最近公共祖先(LCA):

给定一颗有根树，若节点z既是节点x的祖先，也是节点y的祖先，则称z是x,y,的公共祖先。在x,y,的所有公共祖先种，深度最大的一个称为最近公共祖先，记作LCA(x,y)

做法一:向上标记法

从x向上走到根节点，标记所有经过的节点，再从y向上走，当第一次遇到已标记的节点是，那么此节点就是LCA(x,y)
每个询问时间复杂度最坏O(n)

做法二:树上倍增法

fa[i,j]表示从i开始,向上走2^j步所能到走到的节点0<=j<=logn
depth[i]表示深度，也是层数
步骤:
1.先将两个点跳到同一层
2.让两个点同时往上跳,一直跳到他们的最近公共祖先的下一层

具体步骤：
路径做二进制拆分，每个数都能表示为2的幂次和。
设F[x][k]表示x走2^k步到达的节点，若节点不存在或者超出范围，f[x][k]=0
f[x][k]=f[f[x][k-1]][k-1]](x先走2^k步在走2^k)
用BFS预处理每个节点的深度depth[i],f[i][j]
dfs方法

1.先找到深度最大的节点，假设为x
2.把x向上走到与y同一深度（一定可以跳到），也就是依次尝试从节点x向上走2^k步,k从大到小，因为越大越先有可能找到
3.如果x=y，那么此时LCA(x,y)=x，停止查找
4.否则，继续让x和y同时向上走2^k步，与步骤2同理
5.最后x与y只差一步就可以相遇，那么此时LCA(x,y)=f[x][0]
预处理O(nlogn) 每次查询O(logn)

模版题:祖孙询问 最近公共祖先2

tarjan

离线每个询问q[i],先做dfs,把每个点分为三类：当前正在访问的点标记为1,已经回溯过的点标记为2,还未被搜索的点标记为0,那么所有标记为2的点的lca都对应标记为1的点的路径上的一个根节点,所以就可以用并查集维护，找到一个代表节点，作为lca,搜索完该点之后维护一次并查集。
距离 题目

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=1e5+10;
int h[N],e[N*2],ne[N*2],w[N*2],idx;
int depth[N];
int st[N];
int p[N];
int res[N]
vector<pii> query[N];
int n,m;

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int f){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j!=f){
            depth[j]=depth[u]+w[i];
            dfs(j,u);
        }
    }
}

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void tarjan(int u){
    st[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[u];
        if(!st[j]){
            tarjan(j);
            p[j]=u;
        }
    }

    for(auto it:query[u]){
        int y=it.x,id=it.second;
        if(y==2){
            int anc=find(y);
            res[id]=depth[u]+depth[y]-2*depth[anc];
        }
    }
    st[u]=2;
}

void solve(){
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(a==b) continue; 
        query[a].push_back({b,i});
        query[b].push_back({a,i});
    }

    for(int i=1;i<=n;i++) p[i]=i;

    dfs(1,-1);

    tarjan(1);

    for(int i=0;i<m;i++) cout<<res[i]<<endl;
}

int main(){
    int T;
    //cin>>T;
    T=1;
    while(T--){
        solve();
    }
    return 0;
}