[HOJ] 146 - 海綿寶寶之我家離你家多遠

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define N 100005
using namespace std;
struct P{
    int p,c;
};
vector<P> s[N];
int dfs[N],add[N],v[N]={0},dp[N][20]={0};
void dfs_tree(int k,int a,int b,int f){
    int i;
    dfs[k]=a,add[k]=b;
    dp[k][0]=f;
    for(i=0;i<s[k].size();i++){
        P r=s[k][i];
        if(v[r.p]==0){
            v[r.p]=1;
            dfs_tree(r.p,a+1,b+r.c,k);
        }
    }
}
int lca(int x,int y){
    if(dfs[x]>dfs[y]) swap(x,y);
    int d,i;
    d=dfs[y]-dfs[x];
    for(i=18;i>=0;i--)
        if(d&(1<<i))
            y=dp[y][i];
    if(x==y) return x;
    for(i=18;i>=0;i--)
        if(dp[x][i]!=dp[y][i])
            x=dp[x][i],y=dp[y][i];
    return dp[x][0];
}
int main(){
    int n,m,x,y,z,i,j,ans,top=1;
    scanf("%d%d",&n,&m);
    for(i=0;i<n-1;i++){
        scanf("%d%d%d",&x,&y,&z);
        s[x].push_back((P){y,z});
        s[y].push_back((P){x,z});
    }
    v[1]=1;
    dfs_tree(1,0,0,0);
    for(i=1;i<=18;i++)
        for(j=1;j<=n;j++)
            dp[j][i]=dp[dp[j][i-1]][i-1];
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        ans=add[x]+add[y];
        z=lca(x,y);
        ans-=add[z]*2;
        printf("%d\n",ans);
    }
}