#include<bits/stdc++.h>
using namespace std;
const long long N = 500001;
long long dp[21][N];
vector<pair<long long, long long> > adj[N];
long long level[N];
long long dist[N];
void dfs(long long u, long long p){
for(pair<long long, long long> x : adj[u]){
long long v = x.first;
if(v != p){
dp[0][v] = u;
level[v] = level[u] + 1;
dist[v] = dist[u] + x.second;
dfs(v, u);
}
}
}
long long solve(long long x, long long k){
long long val = 0;
while(k > 0){
if(k % 2 == 1){
x = dp[val][x];
}
val++;
k >>= 1;
}
return x;
}
long long solve2(long long a, long long b){
if(level[a] > level[b]){
swap(a, b);
}
long long difference = level[b] - level[a];
b = solve(b, difference);
if(a == b){
return a;
}
for(long long i = 20; i >= 0; i--){
if(dp[i][a] != dp[i][b]){
a = dp[i][a];
b = dp[i][b];
}
}
return dp[0][a];
}
long long dist2(long long a, long long b){
return dist[a] + dist[b] - 2 * dist[solve2(a, b)];
}
int main(){
long long n;
cin >> n;
for(long long i = 0; i < n - 1; i++){
long long 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(long long i = 1; i < 21; i++){
for(long long j = 0; j < n; j++){
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
long long q;
cin >> q;
while(q--){
long long 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 |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
25232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
23748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12116 KB |
Output is correct |
| 2 |
Incorrect |
84 ms |
25232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
