lca

const int maxn = 1e5+5;
vector<pii> G[maxn];
int father[maxn][40];
int deep[maxn];
int n,m;
int dis[maxn];
int head;
void (int u, int f){
    father[u][0] = f;
    deep[u] = deep[f] + 1;
    for(int i = 0;i < G[u].size();i++){
        int v = G[u][i].to;
        if(v == f) continue;
        dis[v] = dis[u] + G[u][i].weight;
        dfs(v, u);
    }
}
void init(){
    for(int j = 0;j <= 30;j++){
        for(int i = 0;i <= n;i++){
            father[i][j] = 0;
        }
    }
    dfs(1,0);
    for(int j = 1;j <= 30;j++){
        for(int i = 1;i <= n;i++){
            father[i][j] = father[father[i][j-1]][j-1];
        }
    }
}
int LCA(int u,int v){
    if(deep[u]<deep[v]){
        swap(u, v);
    }
    int tmp = deep[u] - deep[v];
    for(int i = 0;i < 30;i++){
        if((1<<i) & tmp){
            u = father[u][i];
        }
    }
    if(v == u) return u;
    for(int i = 29;i >= 0;i--){
        //cout<<u<<" "<<v<<endl;
        if(father[u][i] != father[v][i]){
            u = father[u][i];
            v = father[v][i];
        }
    }
    u = father[u][0];
    return u;

}
int q;//查询次数
void init(){
    for(int i = 0 ;i <= n;i++){
        G[i].clear();
    }
    memset(vis,0,sizeof(vis));
    memset(father,0,sizeof(father));
    memset(deep,0,sizeof(deep));
    memset(dis,0,sizeof(dis));
}