1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define MAXN 20002 5  6 using namespace std; 7  8 int n, q, cnt; 9 int head[MAXN], to[MAXN], next[MAXN], val[MAXN], deep[MAXN], f[MAXN][21], dis[MAXN];10 11 inline void add(int x, int y, int z)12 {13     to[cnt] = y;14     val[cnt] = z;15     next[cnt] = head[x];16     head[x] = cnt++;17 }18 19 inline void dfs(int u)20 {21     int i, v;22     deep[u] = deep[f[u][0]] + 1;23     for(i = 0; f[u][i]; i++) f[u][i + 1] = f[f[u][i]][i];24     for(i = head[u]; i != -1; i = next[i])25     {26         v = to[i];27         if(!deep[v])28         {29             f[v][0] = u;30             dis[v] = dis[u] + val[i];31             dfs(v);32         }33     }34 }35 36 inline int lca(int x, int y)37 {38     int i;39     if(deep[x] < deep[y]) swap(x, y);40     for(i = 20; i >= 0; i--)41         if(deep[f[x][i]] >= deep[y])42             x = f[x][i];43     if(x == y) return x;44     for(i = 20; i >= 0; i--)45         if(f[x][i] != f[y][i])46             x = f[x][i], y = f[y][i];47     return f[x][0];48 }49 50 int main()51 {52     int i, x, y, z;53     scanf("%d %d", &n, &q);54     memset(head, -1, sizeof(head));55     for(i = 1; i < n; i++)56     {57         scanf("%d %d %d", &x, &y, &z);58         add(x, y, z);59         add(y, x, z);60     }61     deep[1] = 1;62     dfs(1);63     for(i = 1; i <= q; i++)64     {65         scanf("%d %d", &x, &y);66         printf("%d\n", dis[x] + dis[y] - 2 * dis[lca(x, y)]);67     }68     return 0;69 }