[Link] https://www.acmicpc.net/problem/1761
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define endl "\n"
typedef long long ll;
const int INF = 987654321;
const int MAX = 4e4 + 1;
const int log = 17;
int n, m;
vector<vector<pair<int, int>>> edges;
int dis[MAX][log];
int parent[MAX][log];
int depth[MAX];
void get_root_dfs(int idx) {
for(pair<int,int> p: edges[idx]) {
if(parent[idx][0] == p.first) continue;
parent[p.first][0] = idx;
depth[p.first] = depth[idx] + 1;
dis[p.first][0] = p.second;
get_root_dfs(p.first);
}
}
void calc_sparse() {
for1(i, log) {
for1(j, n + 1) {
parent[j][i] = parent[parent[j][i - 1]][i - 1];
dis[j][i] = dis[j][i-1] + dis[parent[j][i-1]][i-1];
}
}
}
int get_lca(int a, int b) {
if(depth[a] < depth[b]) swap(a, b);
for(int i = log - 1; i >= 0; i--) {
if(depth[a] - depth[b] >= 1 << i) {
a = parent[a][i];
}
}
if(a == b) return a;
for(int i = log - 1; i >= 0; i--) {
if(parent[a][i] != parent[b][i]) {
a = parent[a][i];
b = parent[b][i];
}
}
return parent[a][0];
}
int get_dis(int child, int anc) {
int distance = 0;
for(int i = log - 1; i >= 0; i--) {
if(depth[child] - depth[anc] >= 1 << i) {
distance += dis[child][i];
child = parent[child][i];
}
}
return distance;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
edges.resize(n + 1);
for0(i, n-1) {
int a, b, dis; cin>> a >> b >> dis;
edges[a].push_back(make_pair(b, dis));
edges[b].push_back(make_pair(a, dis));
}
get_root_dfs(1);
calc_sparse();
cin >> m;
for0(i, m) {
int a, b; cin >> a >> b;
int lca = get_lca(a, b);
cout << get_dis(a, lca) + get_dis(b, lca) << endl;
}
return 0;
}