比赛 最近的新题 评测结果 AAAAAAAAAA
题目名称 The tag game 最终得分 100
用户昵称 Menamovic 运行时间 0.075 s
代码语言 C++ 内存使用 4.88 MiB
提交时间 2017-07-01 16:10:45
显示代码纯文本
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn=200010;
vector<int>tree[maxn];
int maxdeep[maxn],deep[maxn],father[maxn];

void dfs(int x,int y,int d)
{
	deep[x]=maxdeep[x]=d;
	father[x]=y;
	for(int i=0;i<(int)tree[x].size();i++)
	{
		int tmp=tree[x][i];
		if(tmp!=y)
		{
			dfs(tmp,x,d+1);
			maxdeep[x]=max(maxdeep[x],maxdeep[tmp]);
		}
	}
}
int main()
{
	freopen("taggame.in","r",stdin);
	freopen("taggame.out","w",stdout);
	int n,x;
	scanf("%d%d",&n,&x);
	int u,v;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	dfs(1,1,0);
	int ans=maxdeep[x]*2;
	for(int i=0,j=x;i<deep[x];i++,j=father[j])
	{
		if(i<deep[j])ans=max(maxdeep[j]*2,ans);
		else break;
	}
	printf("%d\n",ans);
	return 0;
}