记录编号	425257	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	Troywar	是否通过	通过
代码语言	C++	运行时间	0.497 s
提交时间	2017-07-14 21:46:03	内存使用	21.10 MiB

#include<cstdio>
#include<queue>
void read(int &x){
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')   ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
}
const int N=200020;
std::vector<int> hollo[N];
int n,k, head[N],all;
struct DATA{
	int v,last;
}edge[N];
void push(int u,int v){
	edge[++all].v=v;
	edge[all].last=head[u];
	head[u]=all;
}
bool vis[N];int f[N][20],deep[N];
std::queue<int > q;
void bfs(){
    q.push(0);vis[0]=true;
    while(!q.empty()){
        int u=q.front();q.pop();
	    for(int i=1;(1<<i)<=deep[u];i++){
		    f[u][i]=f[f[u][i-1]][i-1];
    	}
	    for(int i=head[u];i;i=edge[i].last){
		    int v=edge[i].v;
    		if(vis[v])continue;
		    deep[v]=deep[u]+1;
	    	f[v][0]=u;
            q.push(v);
    	}
    }
}
int lca(int x,int y){
	if(deep[x]<deep[y])
		x^=y,y^=x,x^=y;
	int t=deep[x]-deep[y];
	for(int i=0;(1<<i)<=t;i++)
		if(t&(1<<i))	x=f[x][i];
	if(x==y)return x;
	for(int i=10;i>=0;i--){
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	}return f[x][0];
}
int main(){
	freopen("cowpol.in","r",stdin);
	freopen("cowpol.out","w",stdout);
	read(n),read(k);
	int pi,ai;
	for(int i=1;i<=n;i++){
		read(ai),read(pi);
		hollo[ai].push_back(i);
		push(pi,i);
	}
    deep[0]=1;bfs();
	for(int i=1;i<=k;i++){
        int u;
        int dep=0;
		int maxn=0;
        for(int j=0;j<hollo[i].size();j++)
            if(dep<deep[hollo[i][j]])
                dep=deep[hollo[i][j]],u=hollo[i][j];
		for(int j=0;j<hollo[i].size();j++){
			int v=hollo[i][j];
			int t=lca(u,v);
			int dis=deep[u]+deep[v]-2*deep[t];
			maxn=dis>maxn?dis:maxn;
		}printf("%d\n",maxn);
	}
}