最近公共祖先

1. 倍增的思想（基于二进制拼凑的思想）

倍增法最重要的思想就是根据二进制思想加上fa和depth数组去实现
fa[][] 数组
depth[] 数组

2：tarjan 离线算法（类似缩点的原理）

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void add(int from,int to,int w)
{
    e[tot].to = to, e[tot].nxt = h[from], e[tot].w = w;
    h[from] = tot ++;
}
void dfs(int u,int fa)
{
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(to == fa) continue;
        dis[to] = dis[u] + e[i].w;
        dfs(to,u);
    }
}
void tarjan(int u)
{
    vis[u] = 1;
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(!vis[to])
        {
            tarjan(to);
            fa[to] = u;
        }
    }
    for(auto nod : query[u])
    {
        int id = nod.second, y = nod.first;
        if(vis[y] == 2)
        {
            res[id] = dis[y] + dis[u] - 2 * dis[find(y)];
        }
    }
    vis[u] = 2;
}

3 RMQ （DFS序 + 区间最小值）