1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = (1); i <= (n); i++)
const int MAX_N = 100005;
const int MAX_LOG = 30;
int p[MAX_N][MAX_LOG], depth[MAX_N], fa[MAX_N];
int cnt;
vector<int> G[MAX_N];
void dfs(int u, int fa, int d) {
    p[u][0] = fa;
    depth[u] = d;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != fa) dfs(v, u, d + 1);
    }
}
void init() {
    dfs(0, -1, 0);
    
    for (int k = 0; k + 1 < MAX_LOG; k++) {
        for (int v = 0; v <= cnt; v++) {
            if (p[v][k] < 0) p[v][k + 1] = -1;
            else p[v][k + 1] = p[p[v][k]][k];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX