2 3 2 1 2 10 3 1 15 1 2 2 3 2 2 1 2 100 1 2 2 1
10 25 100 100
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
int head[40000+10],tail;
struct Edge
{
int val,to,next;
}edge[2*40000+10];
void add(int from,int to,int val)
{
edge[tail].val=val;
edge[tail].to=to;
edge[tail].next=head[from];
head[from]=tail++;
}
int step,fst[40000+10],dth[40000*2+10],dis[40000+10],point[40000*2+10];
bool vis[40000+10];
void dfs(int from,int dep)
{
vis[from]=1;
fst[from]=++step;
dth[step]=dep;
point[step]=from;
for(int i=head[from];i!=-1;i=edge[i].next)
{
int to=edge[i].to,val=edge[i].val;
if(!vis[to])
{
dis[to]=dis[from]+val;
dfs(to,dep+1);
point[++step]=from;
dth[step]=dep;
}
}
}
int dp[40000*2+10][20];
void create(int n)
{
n*=2;
for(int i=0;i<n;i++)
dp[i][0]=i;
for(int j=1;(1<<j)<n;j++)
for(int i=0;i+(1<<j)-1<n;i++)
{
int one=dp[i][j-1],two=dp[i+(1<<j-1)][j-1];
dp[i][j]=dth[one]<dth[two]?one:two;
}
}
int seek(int l,int r)
{
int k,len;
for(k=0,len=r-l+1;(1<<k+1)<=len;k++);
int one=dp[l][k],two=dp[r-(1<<k)+1][k];
return dth[one]<dth[two]?point[one]:point[two];
}
int cnt(int l,int r)
{
int one=fst[l],two=fst[r];
if(one>two)
swap(one,two);
return dis[l]+dis[r]-2*dis[seek(one,two)];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
tail=0;
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from,to,val);
add(to,from,val);
}
dis[1]=0;
memset(vis,0,sizeof(vis));
step=-1;
dfs(1,0);
create(n);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",cnt(l,r));
}
}
}原文：http://blog.csdn.net/stl112514/article/details/44007603