Submission #2165798

---

Source Code Expand

#include<iostream>
#include<cstdio>
#define MN 100000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,head[MN+5],cnt=0,f[MN+5],v[MN+5],ans=0;
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
	e[++cnt]=(edge){t,head[f]};head[f]=cnt;
	e[++cnt]=(edge){f,head[t]};head[t]=cnt;	
}
void dfs(int x,int fa)
{
	int has=0,bad=0;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			dfs(e[i].to,x);
			bad|=(has&f[e[i].to]);
			has|=f[e[i].to];
		}
	for(v[x]=16;~v[x];--v[x]) if(bad&(1<<v[x])) break;
	for(++v[x];has&(1<<v[x]);++v[x]);
	f[x]=(has&((1<<17)-(1<<v[x])))|(1<<v[x]);
	ans=max(ans,v[x]);
}

int main()
{
	n=read();
	for(int i=1;i<n;++i) ins(read(),read());
	dfs(1,0);cout<<ans;
	return 0;
}

Submission Info

Judge Result