Easiest HLD with subtree queries (incomplete)

hld.cpp

// http://codeforces.com/blog/entry/53170
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define eb emplace_back

int n, u, v, q;
int sz[N], in[N], rin[N], out[N], chain[N], t;
vector <int> adj[N];

int dfs_sz(int u = 0, int p = 0) {
    sz[u] = 1;
    if (adj[u][0] == p and adj[u].size() > 1) {
        swap(adj[u][0], adj[u][1]);
    }
    for (int& v : adj[u]) {
        if (v == p) continue;
        sz[u] += dfs_sz(v, u);
        if (sz[v] > sz[adj[u][0]]) {
            swap(v, adj[u][0]);
        }
    }
    return sz[u];
}

void dfs_hld(int u = 0, int p = 0) {
    in[u] = t++;
    rin[in[u]] = u;
    chain[u] = u == adj[p][0] ? chain[p] : u;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_hld(v, u);
    }
    out[u] = t;
}

int main() {
    scanf("%d %d", &n, &q);
    adj[0].eb(1);
    adj[1].eb(0);
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &u, &v);
        adj[u].eb(v);
        adj[v].eb(u);
    }

    dfs_sz();
    dfs_hld();

    printf(" i| rin| in| out| chain|\n");
    for (int i = 0; i <= n; i++) {
        printf("%2d|%4d|", i, rin[i]);
        printf("%3d|%4d|", in[rin[i]], out[rin[i]]);
        printf("%6d|\n", chain[rin[i]]);
    }

    return 0;
}