比赛 |
最近的新题 |
评测结果 |
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;
}