CodeForces - 686D 【树的重心】

传送门：http://codeforces.com/problemset/problem/686/D

题意：给你n个节点，其中1为根， 第二行给你2~n的节点的父亲节点编号。 然后是q个询问，求询问的节点为根的重心的节点编号。

思路：利用树的重心的一个性质：树的重心在 根节点 和 根节点的最大子结点的重心 之间。并且2*cnt[v]>cnt[u]（u为根节点，v为重心）。

代码：

#include<iostream>

#include<vector>

using namespace std;

vector<int>e[300005];

int f[300005];

int cnt[300005];

int ans[300005];

void dfs(int u)

{

    cnt[u] = 1;

    int temp = 0;

    int pos;

    for(int i = 0; i < (int)e[u].size(); i++)

    {

        int v = e[u][i];

        dfs(v);

        if(cnt[v] > temp)

        {

            temp = cnt[v];

            pos = v;

        }

        cnt[u] += cnt[v];

    }

    if(cnt[u] == 1 || cnt[u] == 2)

    {

        ans[u] = u;

        return ;

    }

    pos = ans[pos];

    while(2 * cnt[pos] < cnt[u])

    {

        pos = f[pos];

    }

    ans[u] = pos;

}

int main()

{

    int m, n;

    scanf("%d%d", &n, &m);

    f[1] = 1;

    for(int i = 2; i <= n; i++)

    {

        int x;

        scanf("%d", &x);

        f[i] = x;

        e[x].push_back(i);

    }

    dfs(1);

    for(int i = 1; i <= m; i++)

    {

        int x;

        scanf("%d", &x);

        printf("%d\n", ans[x] );

    }

}