[HOJ] 177 - 地理報告

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define N 100005
int dp[N][20]={0},v[N]={0};
long long int len[N];
struct P{
    int x,y;
};
vector<P> s[N];
int point(int u,int d){
    int i;
    for(i=0;i<18;i++)
        if(d&(1<<i))
            u=dp[u][i];
    return u;
}
void dfs(int u,long long int add,int fa){
    int i;
    dp[u][0]=fa;
    len[u]=add;
    for(i=0;i<s[u].size();i++){
        P vv=s[u][i];
        if(v[vv.x]==0){
            v[vv.x]=1;
            dfs(vv.x,add+vv.y,u);
        }
    }
}
int main(){
    int n,m,i,j,x,y,k;
    long long int ans;
    scanf("%d%d",&n,&m);
    for(i=0;i<n-1;i++){
        scanf("%d%d%d",&x,&y,&k);
        s[x].push_back((P){y,k});
        s[y].push_back((P){x,k});
    }
    v[1]=1;
    dfs(1,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=len[x];
        x=point(x,y);
        ans-=len[x];
        printf("%lld\n",ans);
    }
}