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

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdarg>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <functional>
using namespace std;
#define MAXN 200001
vector<int> G[MAXN];
int size[MAXN], top[MAXN], parent[MAXN];
int deep[MAXN], son[MAXN];
void dfs(int u, int f, int d)
{
    size[u] = 1;
    parent[u] = f;
    deep[u] = d;
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != f)
        {
            dfs(to, u, d+1);
            size[u] += size[to];
            if(size[son[u]] < size[to])
                son[u] = to;
        }
    }
}
void dfs(int u, int tp)
{
    top[u] = tp;
    if(!son[u])return;
    dfs(son[u], tp);
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != parent[u] && to != son[u])
            dfs(to, to);
    }
}
int lca(int u, int v)
{
    int t1 = top[u], t2 = top[v];
    while(t1 != t2)
    {
        if(deep[t1] < deep[t2])
        {
            swap(u, v);
            swap(t1, t2);
        }
        u = parent[t1];
        t1 = top[u];
    }
    return deep[u]<deep[v]?u:v;
}
inline int dist(int u, int v)
{
    return deep[u]+deep[v]-(deep[lca(u, v)]<<1);
}
vector<int> Z[MAXN];
int main()
{
    char *__p__ = (char *)malloc(64<<20)+(64<<20);
    __asm__("movl %0, %%esp\n" :: "r"(__p__));
    freopen("cowpol.in", "r", stdin);
    freopen("cowpol.out", "w", stdout);
    int n, k;
    scanf("%d %d", &n, &k);
    int rt;
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        if(b)
        {
            G[i].push_back(b);
            G[b].push_back(i);
        }else rt = i;
        Z[a].push_back(i);
    }
    dfs(rt, 0, 0);
    dfs(rt, rt);
    for(int i = 1; i <= k; i++)
    {
        int u = 0;
        int ans = 0;
        for(int j = 0; j < Z[i].size(); j++)
            if(deep[Z[i][j]] > deep[u])
                u = Z[i][j];
        for(int j = 0; j < Z[i].size(); j++)
            if(Z[i][j] != u)
                ans = max(ans, dist(u, Z[i][j]));
        printf("%d\n", ans);
    }
    return 0;
}