题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<string.h> #include<cstring> #include<algorithm> #include<set> #include<map> #include<fstream> #include<cstdlib> #include<ctime> #include<list> #include<climits> #include<bitset> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define scd(a) scanf("%d",&a) #define scf(a) scanf("%lf",&a) #define scl(a) scanf("%lld",&a) #define sci(a) scanf("%I64d",&a) #define scs(a) scanf("%s",a) #define left asfdasdasdfasdfsdfasfsdfasfdas1 #define tan asfdasdasdfasdfasfdfasfsdfasfdas typedef long long ll; typedef unsigned int un; const int desll[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; const ll mod=1e9+7; const int maxn=4e4+7; const int maxm=3e8+7; const double eps=1e-4; int m,n; struct node { int b,nex,c; }no[maxn*2]; int head[maxn],sz=0; int add(int a,int b,int c){ no[sz].b=b; no[sz].c=c; no[sz].nex=head[a]; head[a]=sz++; } int father[maxn],tan[maxn*2][30],dep[maxn]; int ar[maxn*2],le,in[maxn]; ll dis[maxn]; void dfs1(int u,int pre){ for(int i=head[u];i!=-1;i=no[i].nex){ int v=no[i].b; if(v==pre)continue; dis[v]=dis[u]+no[i].c; father[v]=u; dep[v]=dep[u]+1; ar[le++]=u; dfs1(v,u); } in[u]=le; ar[le++]=u; } void init() { memset(tan,0,sizeof(tan)); for(int i=0;i<le;i++){ tan[i][0]=ar[i]; } for(int j=1;j<20;j++){ for(int i=le-1;i>=0;i--){ if(i+(1<<j)-1>=le)continue; int x=tan[i][j-1],y=tan[i+(1<<(j-1))][j-1]; if(dep[x]<dep[y])tan[i][j]=x; else tan[i][j]=y; //cout<<i<<" "<<j<<" "<<tan[i][j]<<endl; } } } int sameFather(int a,int b) { a=in[a]; b=in[b]; if(a>b)swap(a,b); int res=floor(log(b-a+1)/log(2)); int x=tan[a][res],y=tan[b-(1<<res)+1][res]; if(dep[x]<dep[y])return x; else return y; } int main() { int t;scd(t); while(t--){ scd(n);scd(m); memset(head,-1,sizeof(head));sz=0; for(int i=1;i<n;i++){ int a,b,c; scd(a);scd(b);scd(c); add(a,b,c); add(b,a,c); } memset(dis,0,sizeof(dis)); memset(dep,0,sizeof(dep)); dep[1]=1; dfs1(1,0); father[1]=0; init(); for(int i=0;i<m;i++){ int a,b; scd(a);scd(b); int x=sameFather(a,b); printf("%d ",dis[a]+dis[b]-2*dis[x]); } } return 0; }