记录编号	38782	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	1.052 s
提交时间	2012-06-13 07:21:34	内存使用	5.84 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

struct edge
{
	int t;
	edge *next;
	edge(int _t,edge *_next):t(_t),next(_next){}
};

struct type
{
	edge *Map[200010];
	void add(int s,int t)
	{
		Map[s]=new edge(t,Map[s]);
		Map[t]=new edge(s,Map[t]);
	}
}D,L;

int N,K;
int ans[200010],fa[200010],d[200010],mdp[200010],A[200010];
bool f[200010];

void dfs(int u,int pre)
{
	for(edge *p=D.Map[u];p;p=p->next)
	{
		int t=p->t;
		if(t!=pre)
		{
			d[t]=d[u]+1;
			dfs(t,u);
		}
	}
}

void work()
{
	for(int i=1;i<=N;i++)
		if(!mdp[A[i]]||d[i]>d[mdp[A[i]]])
			mdp[A[i]]=i;
	for(int i=1;i<=N;i++)
		if(mdp[A[i]]!=i)
			L.add(i,mdp[A[i]]);
}

int getF(int u)
{
	if(fa[u]==u)
		return u;
	else 
		return fa[u]=getF(fa[u]);
}

void solve(int u,int pre)
{
	fa[u]=u;
	for(edge *p=D.Map[u];p;p=p->next)
	{
		int t=p->t;
		if(t!=pre)
			solve(t,u);
	}
	f[u]=true;
	for(edge *p=L.Map[u];p;p=p->next)
	{
		int t=p->t;
		if(f[t])
			ans[A[u]]=max(ans[A[u]],d[t]+d[u]-2*d[getF(t)]);
	}
	fa[u]=pre;
}

int main()
{
	freopen("cowpol.in","r",stdin);
	freopen("cowpol.out","w",stdout);
	scanf("%d%d",&N,&K);
	for(int p,i=1;i<=N;i++)
	{
		scanf("%d%d",&A[i],&p);
		D.add(p,i);
	}
	dfs(1,0);
	work();
	solve(1,0);
	for(int i=1;i<=K;i++)
		printf("%d\n",ans[i]);
	return 0;
}