欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[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);
}