#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
ifstream fin("measurement.in");
ofstream fout("measurement.out");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
using namespace std;
const int mxn = 5e4;
struct th{
int val = 0, sm = 0;
};
int n;
vt<pair<int, int>>adj[mxn + 3];
int depth[mxn + 3] = {0};
th up[mxn][17];
ll res = 0;
int num[mxn + 3] = {0};
int cr = 1;
bool cmp(int a, int b){
return(num[a] < num[b]);
}
void dfs(int s, int pre){
num[s] = cr++;
for(auto i: adj[s]){
if(i.fi == pre)continue;
int v = i.fi, c = i.se;
depth[v] = depth[s] + 1;
up[v][0].val = s; up[v][0].sm = c;
dfs(v, s);
}
}
void build(){
for(int i = 1; i < 17; i++){
for(int j = 1; j <= n; j++){
up[j][i].val = up[up[j][i - 1].val][i - 1].val;
up[j][i].sm = up[j][i - 1].sm + up[up[j][i - 1].val][i - 1].sm;
}
}
}
int find(int a, int b, bool ok){
if(depth[a] < depth[b])swap(a, b);
int k =depth[a] - depth[b];
ll curr = 0;
for(int i = 0; i < 17; i++){
if(k & (1 << i)){
curr += up[a][i].sm;
a = up[a][i].val;
}
}
//cout << curr << " ";
if(a == b){
if(ok)return(curr);
return(a);
}
for(int i = 16; i >= 0; i--){
if(up[a][i].val != up[b][i].val){
curr += up[a][i].sm + up[b][i].sm;
a = up[a][i].val; b = up[b][i].val;
}
}
curr += up[a][0].sm + up[b][0].sm;
if(ok)return(curr);
return(up[a][0].val);
}
int main()
{
LIFESUCKS;
cin >> n;
for(int i = 1; i < n; i++){
int u, v, c; cin >> u >> v >> c;
adj[u].pb({v, c});
adj[v].pb({u, c});
}
dfs(0, -1);
build();
int a[5];
int q; cin >> q;
for(int i = 0; i < q; i++){
for(int j = 0; j < 5; j++)cin >> a[j];
sort(a, a + 5, cmp);
int lca = find(a[1], a[0], false);
for(int j = 2; j < 5; j++){
lca = find(lca, a[j], false);
}
res = find(lca, a[0], true);
for(int j = 1; j < 5; j++){
res += find(a[j], find(a[j - 1], a[j], false), true);
//cout << a[j] << " " << find(a[j], a[j - 1], false) << " " << res << "\n";
}
cout << res << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
12852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
11112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Incorrect |
41 ms |
12852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
