#include<bits/stdc++.h>
using namespace std;
const int N = 500001;
int dp[21][N];
vector<pair<int, int> > adj[N];
int level[N];
int dist[N];
void dfs(int u, int p){
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p){
dp[0][v] = u;
level[v] = level[u] + 1;
dist[v] = dist[u] + x.second;
dfs(v, u);
}
}
}
int solve(int x, int k){
int val = 0;
while(k > 0){
if(k % 2 == 1){
x = dp[val][x];
}
val++;
k >>= 1;
}
return x;
}
int solve2(int a, int b){
if(level[a] > level[b]){
swap(a, b);
}
int difference = level[b] - level[a];
b = solve(b, difference);
if(a == b){
return a;
}
for(int i = 20; i >= 0; i--){
if(dp[i][a] != dp[i][b]){
a = dp[i][a];
b = dp[i][b];
}
}
return dp[0][a];
}
int dist2(int a, int b){
return dist[a] + dist[b] - 2 * dist[solve2(a, b)];
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n - 1; i++){
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back(make_pair(b, c));
adj[b].push_back(make_pair(a, c));
}
dist[0] = 0;
dfs(0, -1);
for(int i = 1; i < 21; i++){
for(int j = 0; j < n; j++){
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
int q;
cin >> q;
while(q--){
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
cout << (dist2(a, b) + dist2(b, c) + dist2(c, d) + dist2(d, e) + dist2(e, a))/2 << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
20992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
19276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12184 KB |
Output is correct |
| 2 |
Incorrect |
76 ms |
20992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
