void dfs(int u){

    for(int i = head[u];i!=-;i = edge.next){

        int to = dege[i].to;

        if(to == p[u][])

           continue;

        d[to] = d[u]+;

        dis[to] = dis[u]+edge[i].w;

        p[to][] = u;

        dfs((to));

    }

}

void init(){

    for(int j = ;(<<j)<=n;j++)

       for(int i = ;(<<i)<=n;i++){

           p[i][j] = p[p[i][j-]][j-];

       }

}

int lca(int a,int b){

    if(d[a]>d[b]) swap(a,b);//b在下面；

    int f = d[b]-d[a];//f是高度差；

    for(int i = ;(<<i)<=f;i++)

       if(((<<i))&f)

          b = p[b][i];

    if(a!=b){

        for(int i = (int lomg2(n));i>=;i--)

            if(p[a][i]!= p[b][i])//从最大的祖先开始，判断a，b的祖先是否相同

               a = p[a][i],b = p[b][i];//如果不相同，a和b同时向上移动2^j

        a = p[a][];

    }

    return a;

}