LCA倍增模版-轉自DS

/*
	首先我們建構一張表P[1,N][1,logN] (這裡P[i][j]指的是結點i的第2^j個祖先)
	P[i][j] = pre[i] // j==0 時
		  P[ P[i][j-1] ][j-1] // 等于P[i][j-1]的第2^(j-1)的父親
*/

const int N=40005;
int pw[20];

struct Edge {
   int b,c,nxt;
}e[99999];
int p[N];
int cnt;
int n,m,q;

//------------------------- LCA倍增法<NlogN,logN> -------------------------
int dis[N],dep[N]; //dis為到根節點的距離,dep為深度
int pa[N][20],pre[N];
void dfs(int u,int f,int deep) { //生成一顆dfs樹
   dep[u]=deep; pre[u]=f;
   for(int i=p[u];i!=-1;i=e[i].nxt) {
      int v=e[i].b;
      int w=e[i].c;
      if(v==f) continue;
      dis[v]=dis[u]+w;
      dfs(v,u,deep+1);
   }
}
void make_pa() { //求倍增祖先
   int i,j;
   memset(pa,-1,sizeof(pa));
   for(i=1;i<=n;i++) pa[i][0]=pre[i];
   for(j=1;pw[j]<n;j++)
      for(i=1;i<=n;i++) if(pa[i][j-1]!=-1)
         pa[i][j]=pa[pa[i][j-1]][j-1];
}
int lca(int x,int y) { //查詢LCA(x,y)
   int i,log=0;
   if(dep[x]<dep[y]) swap(x,y);
   while(pw[log+1]<=dep[x]) log++;
   for(i=log;i>=0;i--)
      if(dep[x]-pw[i]>=dep[y]) x=pa[x][i];
   if(x==y) return x;
   for(i=log;i>=0;i--)
      if(pa[x][i]!=-1&&pa[x][i]!=pa[y][i])
         x=pa[x][i],y=pa[y][i];
   return pre[x];
}
//------------------------- LCA上的RMQ -------------------------
//詢問路徑最大,最小值.
//注意: dis[u]為 v->u 的邊權
int mx[N][20];
int tlog[N];
void make_rmq() {
   int i,j;
   memset(mx,-1,sizeof(mx));
   for(i=1;i<=n;i++) mx[i][0]=dis[i];
   for(j=1;pw[j]<n;j++)
      for(i=1;i<=n;i++) if(pa[i][j-1]!=-1)
         mx[i][j]=max(mx[i][j-1],mx[pa[i][j-1]][j-1]);
}
int get_rmq(int x,int f) {
   if(x==f) return -1;
   int len=dep[x]-dep[f];
   int k=tlog[len];
   int idx=x;
   for(int j=tlog[len-pw[k]];j>=0;j--)
      if(pw[j]&(len-pw[k])) idx=pa[idx][j];
   //printf("``` %d %d , %d %d\n",x,k,idx,k);
   return max(mx[x][k],mx[idx][k]);
}
//------------------------- THE END -------------------------

void addedge(int a,int b,int c) {
   e[cnt].b=b; e[cnt].c=c; e[cnt].nxt=p[a]; p[a]=cnt++;
   e[cnt].b=a; e[cnt].c=c; e[cnt].nxt=p[b]; p[b]=cnt++;
}
void init() {
   for(int i=0;i<20;i++) pw[i]=1<<i;
   memset(p,-1,sizeof(p));
   cnt=0;
}
int main()
{
   int i,j,t,cas=0;
   int a,b,c;
   scanf("%d",&t);
   while(t--) {
      init();
      scanf("%d%d",&n,&m);
      for(i=1;i<n;i++) {
         scanf("%d%d%d",&a,&b,&c);
         addedge(a,b,c);
      }

      dfs(1,1,0);
      make_pa();

      while(m--) {
         scanf("%d%d",&a,&b);
         int f=lca(a,b);
         printf("%d\n",dis[a]+dis[b]-2*dis[f]);
      }
   }
   return 0;
}