vector<int>e[maxn];
int deep[maxn],f[maxn],anc[maxn][25];
void init(){
	mm(f,0),mm(anc,0),mm(deep,0);
	deep[1]=1;
}
void dfs(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i];
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            dfs(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
dfs(1,0);

void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    in[x]=++step;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
    out[x]=step;
} 
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}

void dfs(int id){
    for(int i=0;i<e[id].size();i++){
        int next=e[id][i].to,ww=e[id][i].w;
        if(vis[next]) continue;
        dis[next]=dis[id]+ww;
        vis[next]=1;
        dfs2(next);
    }
}
预处理任意一点的dist(id出发到各点的距离)
树上x到y的距离为dist[x]+dist[y]-2*dist[lca(x,y)]