Heav-light decomposition

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;

struct NodeHLD
{
    int root, parent, depth, subsize, top;
} tree[N];

vector<int> g[N];
int n;

int DFS (int root, int parent, int depth)
{
    tree[root].root=root;
    tree[root].parent=parent;
    tree[root].depth=depth;
    for (int i=0;i<g[root].size();i++)
    {
        int u=g[root][i];
        if (u==parent) continue;
        tree[root].subsize+=DFS (u, root, depth+1);
    }
    return tree[root].subsize;
}

void HLD (int root, int parent, int top)
{
    tree[root].top=top;
    for (int i=0;i<g[root].size();i++)
    {
        int u=g[root][i];
        if (u==parent) continue;
        if (2*tree[u].subsize>tree[root].subsize) HLD (u, root, top);
        else HLD (u, root, u);
    }
}

int LCA (int v, int u)
{
    while (tree[v].top!=tree[u].top)
    {
        if (tree[tree[v].top].depth<tree[tree[u].top].depth) u=tree[tree[u].top].parent;
        else v=tree[tree[v].top].parent;
    }

    if (tree[v].depth<tree[u].depth) return v;
    return u;
}

int main()
{
    return 0;
}