Archie

练习一下树刨

只要记录一下到链顶的距离以及到父亲的距离就行了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct e{
    int to;
    int ne;
    int k;
}ed[50005];
int x,y,z;
int p;
int head[40005];
int son[40005];
int dep[40005];
int len[40005];
int siz[40005];
int top[40005];
int fa[40005];
int dfn[40005];
int rnk[40005];
int lenf[40005];
void add(int f,int to,int v){
    p++;
    ed[p].k=v;
    ed[p].ne=head[f];
    ed[p].to=to;
    head[f]=p;
}
void dfs(int no,int f){
    son[no]=-1;
    siz[no]=1;
    fa[no]=f;
    dep[no]=dep[f]+1;
    for(int i=head[no];i;i=ed[i].ne){
        if(ed[i].to==f) continue;
        dfs(ed[i].to,no);
        siz[no]+=siz[ed[i].to];
        lenf[ed[i].to]=ed[i].k;
        if(son[no]==-1||siz[ed[i].to]>siz[son[no]]){
            son[no]=ed[i].to;
        }
    }
}
int cnt;
void dfs2(int no,int to,int l){
//  cout<<no<<" "<<to<<endl; 
    cnt++;
    dfn[no]=cnt;
    top[no]=to;
    rnk[cnt]=no;
    if(to!=no)
    {
        len[no]=len[fa[no]]+l;
    }
    if(-1==son[no]) return ;
    dfs2(son[no],to,lenf[son[no]]);
    for(int i=head[no];i;i=ed[i].ne){
        if(ed[i].to==fa[no]||ed[i].to==son[no]) continue;
    //  cout<<"S";
        dfs2(ed[i].to,ed[i].to,0);
    }

}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    } 
    dep[1]=1;
    dfs(1,1);
    dfs2(1,1,0);
    while(m--){
        scanf("%d%d",&x,&y);
        int ans=0;
        while(top[x]!=top[y]){
            if(dep[top[x]]>=dep[top[y]]){
                ans+=len[x]+lenf[top[x]]; 
                x=fa[top[x]];

            }else{
                ans+=len[y]+lenf[top[y]];
                y=fa[top[y]];

            }
        } 
        if(dep[x]>dep[y]){

            ans+=len[x]-len[y];
        }else{
            ans+=len[y]-len[x];
        }
        cout<<ans<<endl;;
    }

    return 0;
}