记录编号	222991	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	4.288 s
提交时间	2016-02-06 10:41:59	内存使用	16.23 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 200010
#define M 20
using namespace std;
ifstream in("cowpol.in");
ofstream out("cowpol.out");
int n,K;
vector<int> G[N];
vector<int> F[N];
int deep[N]={0};
int p[N][M]={0};
bool l[N]={0};
int o;
void BFS(int s)
{
	int i,u,v;
	queue<int> q;
	for(i=1;i<=n;i++)l[i]=0;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u]=1;
		for(i=0;i<G[u].size();i++)
		{
			v=G[u][i];
			if(!l[v])
			{
				p[v][0]=u;
				deep[v]=deep[u]+1;
				q.push(v);
			}
		}
	}
}
void LCB(int u)
{
	int i,v;
	l[u]=1;
	for(i=1;i<M;i++)
	{
		p[u][i]=p[p[u][i-1]][i-1];
		if(!p[u][i])break;
	}
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!l[v])LCB(v);
	}
}
int LCA(int u,int v)
{
	int i,d,t;
	if(deep[u]<deep[v])
	{
		t=u;
		u=v;
		v=t;
	}
	d=deep[u]-deep[v];
	for(i=0;i<M;i++)if((1<<i)&d)u=p[u][i];
	if(u==v)return u;
	for(i=M-1;i>=0;i--)
	{
		if(p[u][i]!=p[v][i])
		{
			u=p[u][i];
			v=p[v][i];
		}
	}
	u=p[u][0];
	return u;
}
int dis(int u,int v)
{
	int fa,ans=0;
	fa=LCA(u,v);
	ans=deep[u]+deep[v]-2*deep[fa];
	return ans;
}
void read()
{
	int i,j,u,v,w;
	in>>n>>K;
	for(i=1;i<=n;i++)
	{
		u=i;
		in>>w>>v;
	    F[w].push_back(i);
		if(v==0)continue;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	/*for(i=1;i<=n;i++)
	{
		out<<i<<':';
		for(j=0;j<G[i].size();j++)
		{
			out<<G[i][j]<<' ';
		}
		out<<endl;
	}*/
	BFS(1);
	for(i=1;i<=n;i++)l[i]=0;
	LCB(1);
}
void make(int s)
{
	int i,j,u,v;
	int temp=0,best=0,st=0,en=0;
	u=F[s][0];
	//out<<u<<endl;
	for(i=0;i<F[s].size();i++)
	{
		v=F[s][i];
		//out<<dis(1,3)<<' ';
		temp=dis(u,v);
		if(temp>best)
		{
			best=temp;
			st=v;
		}
	}
	//out<<endl;
	best=0;
	for(i=0;i<F[s].size();i++)
	{
		v=F[s][i];
		temp=dis(st,v);
		if(temp>best)
		{
			best=temp;
			en=v;
		}
	}
	out<<best<<endl;
}
void work()
{
	int i,j;
	/*for(i=1;i<=K;i++)
	{
		for(j=0;j<F[i].size();j++)
		{
			out<<F[i][j]<<' ';
		}
		out<<endl;
	}*/
	for(i=1;i<=K;i++)make(i);
}
int main()
{
	read();
	work();
	return 0;
}