记录编号	52787	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	1.633 s
提交时间	2013-02-16 12:19:28	内存使用	35.12 MiB

#include <fstream>
#include <set>
using namespace std;
ifstream fin("cowpol.in");
ofstream fout("cowpol.out");
const int Mx=500000;
set<int>Set[Mx],Fd[Mx];
int N,K,Root,deep[Mx],Belong[Mx],Ans[Mx],Sus;
bool visited[Mx];
class Node
{
public:
	int Name;
	Node *Prev;
}*last[Mx],*Cl[Mx];
class UFSet
{
public:
	int Prev[Mx];
	UFSet()
	{
		for(int i=0;i<Mx;i++)
			Prev[i]=i;
	}
	int FR(int pos)
	{
		if(Prev[pos]!=pos)
			Prev[pos]=FR(Prev[pos]);
		return Prev[pos];
	}
	void Union(int a,int b)
	{
	int Ra=FR(a),Rb=FR(b);
		Prev[Rb]=Ra;
	}
}UFS;
void Add(int a,int b)
{
Node *temp=new Node;
	temp->Name=b;
	temp->Prev=last[a];
	last[a]=temp;
}
void CAdd(int a,int b)
{
Node *temp=new Node;
	temp->Name=b;
	temp->Prev=Cl[a];
	Cl[a]=temp;
}
void GetDeep(int pos,int D)
{
	deep[pos]=D;
	for(Node *temp=last[pos];temp;temp=temp->Prev)
		GetDeep(temp->Name,D+1);
}
void Initialize()
{
int i,Bl,Prev;
	fin>>N>>K;
	for(i=1;i<=N;i++)
		last[i]=Cl[i]=NULL;
	for(i=1;i<=N;i++)
	{
		fin>>Bl>>Prev;
		if(Prev==0)
			Root=i;
		Belong[i]=Bl;
		Set[Bl].insert(i);
		Add(Prev,i);
	}
	GetDeep(Root,1);
	for(i=1;i<=N;i++)
	{
	int Max=0,Mp;
	set<int>::iterator it=Set[i].begin(),en=Set[i].end();
		for(;it!=en;it++)
			if(Max<deep[*it])
			{
				Max=deep[*it];
				Mp=*it;
			}
		for(it=Set[i].begin();it!=en;it++)
			if(*it!=Mp)
			{
				CAdd(Mp,*it);
				CAdd(*it,Mp);
			}
	}
}
void Gdt(int pos)
{
/*set<int>::iterator it=Fd[pos].begin(),en=Fd[pos].end();
	for(;it!=en;it++)
		if(visited[*it])
		{
		int LCA=UFS.FR(*it);
			Ans[Belong[*it]]=max(Ans[Belong[*it]],deep[*it]-deep[LCA]+deep[pos]-deep[LCA]);
		}*/
	for(Node *p=Cl[pos];p;p=p->Prev)
		if(visited[p->Name])
		{
		int LCA=UFS.FR(p->Name);
			Ans[Belong[p->Name]]=max(Ans[Belong[p->Name]],deep[p->Name]-deep[LCA]+deep[pos]-deep[LCA]);
		}
}
void FLCA(int pos)
{
	visited[pos]=true;
	for(Node *p=last[pos];p;p=p->Prev)
	{
		FLCA(p->Name);
		UFS.Union(pos,p->Name);
	}
	Gdt(pos);
}
int main()
{
	Initialize();
	
	FLCA(Root);
	
	for(int i=1;i<=K;i++)
		fout<<Ans[i]<<endl;
	fin.close();
	fout.close();
	return 0;
}