CF685B Kay and Snowflake

题目链接：​​传送门​​ 给出q组询问每次求以这个点为根的子树的重心，n,q<=300000

树的重心的一个性质：每棵的子树的大小都不超过整个树大小的一半
具体细节看代码实现

 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
    int next, to;
}e[A];
int head[A], num;
void add(int fr, int to) {
    e[++num].next = head[fr];
    e[num].to = to;
    head[fr] = num;
}
int n, q, a, siz[A], son[A], fa[A];
void dfs(int fr) {
    son[fr] = fr; siz[fr] = 1;
    for (int i = head[fr]; i; i = e[i].next) {
        int ca = e[i].to;
        if (ca == fa[fr]) continue;
        dfs(ca);
        siz[fr] += siz[ca];
    }
    for (int i = head[fr]; i; i = e[i].next) {
        int ca = e[i].to;
        if (ca == fa[fr]) continue;
        if (siz[ca] * 2 > siz[fr]) son[fr] = son[ca]; //在子树中初步找重心
    }
    while ((siz[fr] - siz[son[fr]]) * 2 > siz[fr]) son[fr] = fa[son[fr]]; //当前节点的重心在子树重心到当前节点的路径上，根据性质判断重心
}

int main(int argc, char const *argv[]) {
    cin >> n >> q;
    for (int i = 2; i <= n; i++) cin >> fa[i], add(i, fa[i]), add(fa[i], i);
    dfs(1);
    while (q--) {
        cin >> a;
        cout << son[a] << endl;
    }
    return 0;
}