/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 5ms 3.684 MiB
#2 Accepted 2ms 3.805 MiB
#3 Accepted 3ms 2.309 MiB
#4 Accepted 3ms 3.562 MiB
#5 Accepted 2ms 3.188 MiB
#6 Accepted 2ms 3.562 MiB
#7 Accepted 2ms 3.801 MiB
#8 Accepted 3ms 2.438 MiB
#9 Accepted 6ms 3.434 MiB
#10 Accepted 15ms 3.934 MiB

代码

#include<bits/stdc++.h>
const int maxn=200001;
inline const void read(int &a)
{
	a=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
inline const void write(int a)
{
	if(a>=10)write(a/10);
	putchar(a%10+'0');
}
inline const int max(int a,int b)
{
	if(a>b)return a;
	return b;
}
inline const int min(int a,int b)
{
	if(a<b)return a;
	return b;
}
int point[maxn],n,d=0,ans=0,to[maxn],next[maxn],start,end,dis[maxn];
bool been[maxn],on_chain[maxn];
void dfs1(int p,int tt)
{
	if(tt==1&&dis[p]>dis[start])start=p;
	if(tt==2&&dis[p]>dis[end])end=p;
	been[p]=true;
	int side=point[p];
	while(side)
	{
		if(!been[to[side]])
		{
			dis[to[side]]=dis[p]+1;
			dfs1(to[side],tt);
		}
		side=next[side];
	}
}
bool dfs2(int p)
{
	if(p==end){on_chain[p]=true;return true;}
	been[p]=true;
	int side=point[p];
	while(side)
	{
		if(!been[to[side]])if(dfs2(to[side]))on_chain[p]=true;
		side=next[side];
	}
	if(on_chain[p])return true;
	else return false;
}
void dfs3(int p)
{
	if(on_chain[p])dis[p]=0;
	if(dis[p]>dis[ans])ans=p;
	been[p]=true;
	int side=point[p];
	while(side)
	{
		if(!been[to[side]])
		{
			dis[to[side]]=dis[p]+1;
			dfs3(to[side]);
		}
		side=next[side];
	}
}
inline const void add(int a,int b)
{
	next[++d]=point[a];
	point[a]=d;
	to[d]=b;
}
inline const void init()
{
	memset(dis,0,sizeof(dis));
	memset(been,false,sizeof(been));
}
int main()
{
	//freopen("测试数据.txt","r",stdin);
	memset(on_chain,false,sizeof(on_chain));
	memset(point,0,sizeof(point));
	read(n);
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		read(a);read(b);
		add(a,b);add(b,a);
	}
	init();
	dfs1(1,1);
	init();
	dfs1(start,2);
	init();
	dfs2(start);
	init();
	dfs3(start);
	write(dis[ans]);
	return 0;
}

信息

递交者
类型
递交
题目
树T1
题目数据
下载
语言
C++
递交时间
2017-09-21 16:37:19
评测时间
2017-09-21 16:37:19
评测机
分数
10
总耗时
48ms
峰值内存
3.934 MiB