记录编号	252148	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	1.528 s
提交时间	2016-04-19 16:23:39	内存使用	10.76 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=200000+10;
vector<int>v[maxn];
vector<int>d[maxn];
vector<int>Q[maxn];
vector< pair<int,int> >LCA[maxn];
bool vis[maxn];
int deep[maxn],f[maxn],zx[maxn],Aim[maxn],n,m/*,rak[maxn]*/;

int find(int x){return x==f[x]? x:f[x]=find(f[x]);}

void un(int x,int y){
	int p=find(x),q=find(y);
	if (p==q) return;
	f[q]=p;
}

void DFS(int x,int dep){//处理出节点深度
	vis[x]=1;
	for (int i=0;i<v[x].size();++i)
	   if (!vis[v[x][i]]){
		  deep[v[x][i]]=dep+1;
		  DFS(v[x][i],dep+1);
	   }
}

void tarjan(int x){//求LCA
	zx[find(x)]=x;
	for (int i=0;i<v[x].size();++i){
		if (f[v[x][i]]==v[x][i]){
			tarjan(v[x][i]);
			un(x,v[x][i]);
		    zx[find(x)]=x;
		}

	}
	vis[x]=1;
	for (int i=0;i<Q[x].size();++i)
		if (vis[Q[x][i]]){
		   LCA[x].push_back(make_pair(Q[x][i],zx[find(Q[x][i])]));
		   LCA[Q[x][i]].push_back(make_pair(x,zx[find(Q[x][i])]));
		}
}

int main(){
	freopen("cowpol.in","r",stdin);
	freopen("cowpol.out","w",stdout);
	int __size__ = 30 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	scanf("%d%d",&n,&m); int root=1;
	for(int i=1;i<=n;++i) f[i]=i/*,rak[i]=0*/;
	for (int i=1;i<=n;++i){
		int x,y; scanf("%d%d",&x,&y);
		d[x].push_back(i);//党
		if (y!=0) v[y].push_back(i);//树
		if (!y) root=i;
	}
	deep[root]=0;
	DFS(root,0);
	for (int i=1;i<=m;++i){//处理出需要查询的点对
	   int maxd=-1,poi,V;
	   for (int j=0;j<d[i].size();++j)
		  if (deep[d[i][j]]>maxd){
				maxd=deep[d[i][j]];
				poi=d[i][j];
		  }
	   Aim[i]=poi;
	   for (int j=0;j<d[i].size();++j)
		  if (d[i][j]!=poi){
				int u=poi;V=d[i][j];
				Q[u].push_back(V);
				Q[V].push_back(u);
		  }
    }
    for (int i=1;i<=n;++i) vis[i]=0;
	tarjan(root);
	for (int i=1;i<=m;++i){
		int u=Aim[i],now=-1;
		for (int k=0;k<LCA[u].size();++k){
			int V=LCA[u][k].first;
			int dist=deep[u]+deep[V]-deep[LCA[u][k].second]*2;
			if (dist>now) now=dist;
		}
		printf("%d\n",now);
	}
}