记录编号	270961	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.614 s
提交时间	2016-06-15 15:29:58	内存使用	19.77 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int read(){
	int x=0, f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){
 		if(ch=='-') f=-1;
 		ch=getchar();
 	}
 	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int maxn = 300010;

struct Edge{
	int next, to;
}e[maxn<<1], gay[maxn<<1];
int head[maxn], tot, gays[maxn], totg;
void Add_Edge(int u, int v){
	e[++tot].next = head[u];
	e[tot].to = v;
	head[u] = tot;
}
void Add_Gay(int u, int v){
	gay[++totg].next = gays[u];
	gay[totg].to = v;
	gays[u] = totg;
}

int N, K, s;
int fa[maxn], size[maxn], son[maxn], depth[maxn], first[maxn];
int dfn[maxn], top[maxn], dfn_order;

void dfs1(int x){
	size[x] = 1;
	for(int i=head[x]; i; i=e[i].next){
		int to = e[i].to;
		if(size[to]) continue;
		depth[to] = depth[x]+1;
		dfs1(to);
		size[x] += size[to];
		if(size[to] > size[son[x]]) son[x] = to;
	}
}
void dfs2(int x, int tp){
	top[x] = tp;
	dfn[x] = ++dfn_order;
	if(son[x]) dfs2(son[x], tp);
	for(int i=head[x]; i; i=e[i].next){
		int to = e[i].to;
		if(!dfn[to]) dfs2(to, to);
	}
}

int lca(int x, int y){
	while(top[x] != top[y]){
		if(depth[top[x]] < depth[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	return (depth[x] < depth[y])?x:y;
}

inline void Init(){
	N = read(), K = read();
	for(int i=1; i<=N; ++i){
		int A = read(), P = read();
		if(!first[A]) first[A] = i;
		Add_Gay(A, i); 
		if(!P){s = i; continue;}
		fa[i] = P;
		Add_Edge(P, i);
	}
}
inline void Build(){
	dfs1(s);
	dfs2(s, s);
}
inline void Solve(){
	for(int i=1; i<=K; ++i){
		int a = first[i], b, maxk = 0, k = 0;
		for(int j=gays[i]; j; j=gay[j].next){
			b = gay[j].to;
			if(a==b) continue;
			int newk = depth[a]+depth[b]-2*depth[lca(a, b)];
			if(maxk < newk)	maxk = newk, k = b;
		}
		//printf("%d %d %d %d\n", i, a, maxk, k);
		maxk = 0, a = k;
		for(int j=gays[i]; j; j=gay[j].next){
			b = gay[j].to;
			if(a==b) continue;
			int newk = depth[a]+depth[b]-2*depth[lca(a, b)];
			if(maxk < newk)	maxk = newk, k = b;
		}
		printf("%d\n", maxk);
	}
		//getchar();
}
int main(){
	freopen("cowpol.in","r",stdin);	freopen("cowpol.out","w",stdout);
	Init();
	Build();
	Solve();
	return 0;
}