比赛 20120612 评测结果 AAAAAAAAAAAAA
题目名称 政党 最终得分 100
用户昵称 kaaala 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-06-12 17:19:50
显示代码纯文本
#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;
}