• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# #10134. 「一本通 4.4 练习 1」Dis

3小时前 1次浏览

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 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];
p++;
ed[p].k=v;
ed[p].to=to;
}
void dfs(int no,int f){
son[no]=-1;
siz[no]=1;
fa[no]=f;
dep[no]=dep[f]+1;
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]]);
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);
}
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;
}
``````