树链剖分+LCA

树链剖分？树论糕手的第一步！

时间复杂度O(0.37nlogn)

vector<int> tr[N];
int big[N], siz[N], top[N], fa[N], depth[N], idx;
void dfs1(int &u, int f) //预处理1
{
    siz[u]++;
    fa[u] = f;
    depth[u] = depth[f] + 1;
    for (auto v : tr[u])
        if (v != f)
        {
            dfs1(v, u);
            siz[u] += siz[v];
            if (!big[u] || siz[big[u]] < siz[v])
                big[u] = v;
        }
}
void dfs2(int &u, int f, int &t) //预处理2
{
    top[u] = t; // 记录重链的头
    if (big[u])
        dfs2(big[u], u, t);
    for (int v : tr[u])
        if (v != f && v != big[u])
            dfs2(v, u, v);
}
int lca(int u, int v)
{
    while (top[u] != top[v])
        depth[top[u]] > depth[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
    return depth[u] > depth[v] ? v : u;
}