记录编号	342234	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	2.579 s
提交时间	2016-11-08 10:26:28	内存使用	29.00 MiB

#include<iostream>
#include<vector>
#include<queue> 
#include<cstdio>
#include <cstdlib> 
#define maxn 400050
using namespace std;
struct node {
	int fr, to, v;
	int ne;
} e1[maxn], e2[2*maxn];
int head1[maxn], head2[maxn];
int tot1, tot2;
vector<int> po[maxn];
int maxi[maxn];
int be[maxn];
int deep[maxn];
int n, k;
 
class union_find_set{
private:
	int fa[maxn];
public:
	void beg() {
		for(int i = 1; i <= n; i++) {
			fa[i] = i;
		}
	}
	int find_fa(int a) {
		return fa[a] = a == fa[a] ? a : find_fa(fa[a]);
	}
	bool is_same(int a, int b) {
		return find_fa(a) == find_fa(b);
	}
	void union_set(int a, int b) {
		int faa = find_fa(a), fab = find_fa(b);
		if(faa == fab) return;
		fa[fab] = faa;
	}
}ufs;
 
 
bool vis[maxn];
void dfs_solve(int now) {
//	printf("%d\n",now);
	vis[now] = true;
	for(int i = head1[now]; i; i = e1[i].ne) {
		if(vis[e1[i].to]) continue;
		dfs_solve(e1[i].to);
		ufs.union_set(now,e1[i].to);
	}
//	bel = be[now];
	for(int i = 0; i < po[now].size(); i++) {
		if(!vis[po[now][i]]) continue;
		maxi[be[now]] = max(maxi[be[now]], deep[now]+deep[po[now][i]]-2*deep[ufs.find_fa(po[now][i])]);
	}
}
 
 
void bfs() {
	queue<int> q;
	q.push(0);
	int now, to;
	while(!q.empty()) {
		now = q.front(); q.pop();
		for(int i = head1[now]; i; i = e1[i].ne) {
			to = e1[i].to;
			deep[to] = deep[now]+1;
			q.push(to);
		}
	}
}
 
 
int tmp[maxn];
void handle() {
	for(int i = 1; i <= n; i++) {
		if(deep[i] > deep[tmp[be[i]]]) {
			tmp[be[i]] = i;
		}
	}
	for(int i = 1; i <= n; i++) {
		if(tmp[be[i]] == i) continue;
		po[i].push_back(tmp[be[i]]);
		po[tmp[be[i]]].push_back(i); 
	}
}
 
 
void solve() {
	ufs.beg();
	bfs();
	handle();
	dfs_solve(0);
	for(int i = 1; i <= k; i++) {
		printf("%d\n",maxi[i]);
	}
}
 
 
void read() {
	scanf("%d %d", &n, &k);
	int v, fa;
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &v, &fa);
		++tot1; e1[tot1].fr = fa; e1[tot1].to = i;
		e1[tot1].ne = head1[fa]; head1[fa] = tot1;
		be[i] = v;
		++tot2; e2[tot2].to = i;
		e2[tot2].ne = head2[v]; head2[v] = tot2;
	}
}
 
 
int main() {
	freopen("cowpol.in","r",stdin);
	freopen("cowpol.out","w",stdout);
	int __size__= 64 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	read();
	solve();
	return 0;
}