1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define per(i, a, b) for(int i = (a); i >= (int)(b); --i)
#define debug(x) cerr << #x << ' ' << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 7;
int dep[MAXN], dis[MAXN], f[MAXN][20];
vector<pii> G[MAXN];
void dfs(int x, int last = 0, int fa = -1) {
f[x][0] = fa;
dep[x] = dep[fa] + 1;
dis[x] = dis[fa] + last;
for(int i = 1; (1<<i) <= dep[x]; ++i){
f[x][i] = f[f[x][i-1]][i-1];
}
rep(i, 0, G[x].size()-1){
pii p = G[x][i];
if(p.first == fa) continue;
dfs(p.first, p.second, x);
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int dif = dep[u] - dep[v];
per(i, 20, 0){
if((1<<i) <= dif){
dif -= (1<<i);
u = f[u][i];
}
}
if(u == v) return u;
per(i, 20, 0){
if(dep[u] >= (1<<i) && f[u][i] != f[v][i]){
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
int main() {
int n;
scanf("%d", &n);
int u, v, c;
rep(i, 1, n-1){
scanf("%d %d %d", &u, &v, &c);
G[u].push_back(make_pair(v, c));
G[v].push_back(make_pair(u, c));
}
dfs(0);
int T;
scanf("%d", &T);
while(T--){
scanf("%d %d", &u, &v);
printf("%d\n", dis[u] + dis[v] - 2 * dis[lca(u, v)]);
}
return 0;
}
|
