记录编号	499228	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	1.221 s
提交时间	2018-07-01 17:40:35	内存使用	96.07 MiB

#include<iostream>
#include "cstdio"
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
int n,k,N;
int deep[200001];
int mapa = 0;
std::vector<int> e[200001],party[100001];
int grand[200001][60],gw[200001][60];
//void dfs(int r)
//{
//	for (int i = 1; i <= N; ++i)       
//		grand[r][i] = grand[grand[r][i-1]][i-1];
//    for (int i = 0; i < e[r].size(); ++i)
//       if(e[r][i] != grand[r][0])
//       {
//           deep[e[r][i]] = deep[r]+1;
//           dfs(e[r][i]);
//        }
//}
queue<int> q;
void bfs(int r)
{
	q.push(r);
	while(!q.empty())
	{
		int h = q.front();
		q.pop();
		for (int i = 1; (1<<i) <= deep[h]; ++i)      
			grand[h][i] = grand[grand[h][i-1]][i-1];
		for (int i = 0; i < e[h].size(); ++i)
		{
			if(e[h][i] != grand[h][0])
			{
				deep[e[h][i]] = deep[h]+1;
				q.push(e[h][i]);
			}
		}
	}
}
int lca(int x,int y)
{
    int ans  = 0;
    if(deep[x] > deep[y])
        swap(x,y);
    for (int i = N; i >= 0; --i)
        if (deep[x]<deep[y]&&grand[y][i]&&deep[grand[y][i]] >= deep[x])
        {
            y = grand[y][i];
            ans+=(1<<i);
        }
    if(x == y)
        return ans;
    for (int i = N; i >= 0; --i)
        if (grand[x][i]!=grand[y][i])
        {
            ans+= 2*(1<<i);
            x = grand[x][i];y = grand[y][i];
        }
    if (x != y)
        ans+=2;
    return ans;
}
int main()
{
 
    int start;
 	freopen("cowpol.in","r",stdin);
	freopen("cowpol.out","w",stdout);
    cin >> n >> k;
    N = floor(log(n + 0.0) / log(2.0));
    for (int i = 1; i <= n; ++i)
    {
        int  t;
        cin >> t >> grand[i][0];
        if (grand[i][0] == 0)
            start = i;
        party[t].push_back(i);
        e[i].push_back(grand[i][0]);
        e[grand[i][0]].push_back(i);
    }
	int nkanscanc;
    bfs(start);
    for (int i = 1; i <= k; ++i)
    {
        int deeep = 0,jb,ans = 0;
        for (int j = 0; j < party[i].size(); ++j)
            if(deeep<deep[party[i][j]])
            {
                deeep = deep[party[i][j]];
                jb = party[i][j];
            }        
        for (int j = 0; j < party[i].size(); ++j)
            ans = max(ans,lca(jb,party[i][j]));
        cout << ans << endl;
    }
    return 0;
}