练习一下树刨
只要记录一下到链顶的距离以及到父亲的距离就行了
#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;
}