题目#

1
#include<bits/stdc++.h>
2
#define rep(i, a, b)    for(int i = (a); i <= (int)(b); ++i)
3
#define per(i, a, b)    for(int i = (a); i >= (int)(b); --i)
4
#define debug(x)    cerr << #x << ' ' << x << endl;
5
using namespace std;
6

7
typedef long long ll;
8
typedef pair<int, int> pii;
9
const int MAXN = 2e5 + 7;
10

11
int dep[MAXN], dis[MAXN], f[MAXN][20];
12
vector<pii> G[MAXN];
13

14
void dfs(int x, int last = 0, int fa = -1) {
15
    f[x][0] = fa;
16
    dep[x] = dep[fa] + 1;
17
    dis[x] = dis[fa] + last;
18
    for(int i = 1; (1<<i) <= dep[x]; ++i){
19
        f[x][i] = f[f[x][i-1]][i-1];
20
    }
21
    rep(i, 0, G[x].size()-1){
22
        pii p = G[x][i];
23
        if(p.first == fa)   continue;
24
        dfs(p.first, p.second, x);
25
    }
26
}
27

28
int lca(int u, int v) {
29
    if(dep[u] < dep[v]) swap(u, v);
30
    int dif = dep[u] - dep[v];
31
    per(i, 20, 0){
32
        if((1<<i) <= dif){
33
            dif -= (1<<i);
34
            u = f[u][i];
35
        }
36
    }
37
    if(u == v)  return u;
38
    per(i, 20, 0){
39
        if(dep[u] >= (1<<i) && f[u][i] != f[v][i]){
40
            u = f[u][i];
41
            v = f[v][i];
42
        }
43
    }
44
    return f[u][0];
45
}
46
int main() {
47
    int n;
48
    scanf("%d", &n);
49
    int u, v, c;
50
    rep(i, 1, n-1){
51
        scanf("%d %d %d", &u, &v, &c);
52
        G[u].push_back(make_pair(v, c));
53
        G[v].push_back(make_pair(u, c));
54
    }
55
    dfs(0);
56
    int T;
57
    scanf("%d", &T);
58
    while(T--){
59
        scanf("%d %d", &u, &v);
60
        printf("%d\n", dis[u] + dis[v] - 2 * dis[lca(u, v)]);
61
    }
62
    return 0;
63
}