[Gym] - 100886K 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest K - Toll Roads
程序员文章站
2022-05-22 10:50:19
...
差点因为读漏条件凉凉
枚举free链的一个头,将其提根进行类dp的计算(提根后只需考虑向下的边)
对于根到某个点的答案,可以依靠维护子树内最长链、一段为子树根的最长链、子树外最长链、子树外一端在free链上的最长链这四个信息得到。
因为转移的需求不能只记最大,可能需要次大和第三大。
情况比较多合并注意不要漏,以及边界问题小心初值不合适
#include<bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
#define N 5005
vector<int> e[N];
int n,ans=233333333,op,op1,op2,rt,dep[N],len[N],half[N],K;
void dfs(int k,int fa=0)
{
dep[k]=dep[fa]+1;
len[k]=half[k]=0;
for (auto v:e[k]) if (v!=fa)
{
dfs(v,k);
len[k]=max(max(len[k],len[v]),half[k]+half[v]+1);
half[k]=max(half[k],half[v]+1);
}
}
void solve(int k,int fa=0,int Len=0,int Half=0)
{
if (dep[k]>K) return;
int tmp=max(max(Len,len[k]),Half+half[k]);
if (tmp<ans || (tmp==ans && dep[k]<op))
{
op=dep[k];
ans=tmp;
op1=rt-1;
op2=k-1;
}
int l1=0,l2=0,h1=-1,h2=-1,h3=-1;
for (auto v:e[k]) if (v!=fa)
{
if (len[v]>l2) l2=len[v];
if (l2>l1) swap(l1,l2);
if (half[v]>h3) h3=half[v];
if (h3>h2) swap(h2,h3);
if (h2>h1) swap(h1,h2);
}
for (auto v:e[k]) if (v!=fa)
{
int merge=h1+h2+2;
if (half[v]==h1) merge=h2+h3+2;
else if (half[v]==h2) merge=h1+h3+2;
int len_son=len[v]==l1?l2:l1;
int half_son=half[v]==h1?h2:h1;
solve(v,k,max(max(len_son,Len),max(merge,Half+1+half_son)),max(Half,half_son+1));
}
}
int main()
{
scanf("%d%d",&n,&K);
dep[0]=-1;
for (int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),u++,v++,e[u].pb(v),e[v].pb(u);
for (rt=1;rt<=n;rt++) dfs(rt),solve(rt);
printf("%d\n%d\n",ans,op);
if (op==0) return 0;
printf("%d %d\n",op1,op2);
}
上一篇: 2015-2016 Petrozavodsk Winter Training Camp, SPb SU + SPb AU Contest Greedy Game
下一篇: Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines
推荐阅读
-
[Gym] - 100886K 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest K - Toll Roads
-
Gym - 100886I 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest I - Archaeological Res
-
Gym - 100886B 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest B - Game on Bipartite
-
2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest(Gym 100962)
-
Gym - 100886F 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest F - Empty Vessels
-
题解:2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest