#include <bits/stdc++.h>
using namespace std;
void setIO(string name) {
#ifdef DEBUG
#else
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
#endif
}
#define int long long
const int N = 5e4 + 10;
const int LG = log2(N) + 10;
int n,q,timer = 0,l;
vector<pair<int,int>> adj[N];
// array<int,3> edges[N];
int rdist[N],tin[N],tout[N], lcst[N][LG];
void dfs0(int i,int p){
tin[i] = ++timer;
lcst[i][0] = p;
for(int _ = 1;_<=l;_++){
lcst[i][_] = lcst[lcst[i][_ - 1]][_ - 1];
}
for(auto e : adj[i]){
if(e.first == p)continue;
rdist[e.first] = rdist[i] + e.second;
dfs0(e.first,i);
}
tout[i] = ++timer;
}
inline int is_ansestor(int u,int v){
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lca(int a,int b){
if(is_ansestor(a,b))
return a;
if(is_ansestor(b,a))
return b;
for(int i =l;i>=0;i--){
if(!is_ansestor(lcst[a][i], b))
a = lcst[a][i];
}
return lcst[a][0];
}
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin >> n;
l = ceil(log2(n));
for(int i = 0;i<n - 1;i++){
int a,b,w;cin >> a >> b >> w;
adj[a].push_back({b,w});
adj[b].push_back({a,w});
// edges[i] = {a,b,w};
}
rdist[0] = 0;
dfs0(0,0);
int q;cin >> q;
while(q--){
array<int,5> nums;
for(auto &e : nums)cin >> e;
sort(nums.begin(),nums.end(), [&](int a,int b){
return tin[a] < tin[b];
});
int ans = 0;
for(unsigned i = 0;i<nums.size();i++){
int j = (i + 1)%nums.size();
int a = nums[i],b = nums[j];
int anc = lca(a,b);
ans += rdist[a] + rdist[b] - 2*rdist[anc];
}
ans /= 2;
cout << ans << "\n";
}
}
Compilation message
roadsideadverts.cpp: In function 'void setIO(std::string)':
roadsideadverts.cpp:7:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:8:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
17036 KB |
Output is correct |
2 |
Correct |
76 ms |
18412 KB |
Output is correct |
3 |
Correct |
50 ms |
18416 KB |
Output is correct |
4 |
Correct |
50 ms |
18508 KB |
Output is correct |
5 |
Correct |
53 ms |
18504 KB |
Output is correct |
6 |
Correct |
54 ms |
18440 KB |
Output is correct |
7 |
Correct |
52 ms |
18508 KB |
Output is correct |
8 |
Correct |
55 ms |
18508 KB |
Output is correct |
9 |
Correct |
48 ms |
18452 KB |
Output is correct |
10 |
Correct |
50 ms |
18440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
15704 KB |
Output is correct |
2 |
Correct |
49 ms |
17908 KB |
Output is correct |
3 |
Correct |
50 ms |
17740 KB |
Output is correct |
4 |
Correct |
45 ms |
17768 KB |
Output is correct |
5 |
Correct |
46 ms |
17780 KB |
Output is correct |
6 |
Correct |
49 ms |
17740 KB |
Output is correct |
7 |
Correct |
47 ms |
17816 KB |
Output is correct |
8 |
Correct |
47 ms |
17740 KB |
Output is correct |
9 |
Correct |
52 ms |
17784 KB |
Output is correct |
10 |
Correct |
45 ms |
17792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
2 |
Correct |
54 ms |
17036 KB |
Output is correct |
3 |
Correct |
76 ms |
18412 KB |
Output is correct |
4 |
Correct |
50 ms |
18416 KB |
Output is correct |
5 |
Correct |
50 ms |
18508 KB |
Output is correct |
6 |
Correct |
53 ms |
18504 KB |
Output is correct |
7 |
Correct |
54 ms |
18440 KB |
Output is correct |
8 |
Correct |
52 ms |
18508 KB |
Output is correct |
9 |
Correct |
55 ms |
18508 KB |
Output is correct |
10 |
Correct |
48 ms |
18452 KB |
Output is correct |
11 |
Correct |
50 ms |
18440 KB |
Output is correct |
12 |
Correct |
38 ms |
15704 KB |
Output is correct |
13 |
Correct |
49 ms |
17908 KB |
Output is correct |
14 |
Correct |
50 ms |
17740 KB |
Output is correct |
15 |
Correct |
45 ms |
17768 KB |
Output is correct |
16 |
Correct |
46 ms |
17780 KB |
Output is correct |
17 |
Correct |
49 ms |
17740 KB |
Output is correct |
18 |
Correct |
47 ms |
17816 KB |
Output is correct |
19 |
Correct |
47 ms |
17740 KB |
Output is correct |
20 |
Correct |
52 ms |
17784 KB |
Output is correct |
21 |
Correct |
45 ms |
17792 KB |
Output is correct |
22 |
Correct |
51 ms |
17140 KB |
Output is correct |
23 |
Correct |
55 ms |
16044 KB |
Output is correct |
24 |
Correct |
61 ms |
18156 KB |
Output is correct |
25 |
Correct |
58 ms |
18168 KB |
Output is correct |
26 |
Correct |
62 ms |
18088 KB |
Output is correct |
27 |
Correct |
62 ms |
18184 KB |
Output is correct |
28 |
Correct |
61 ms |
18092 KB |
Output is correct |
29 |
Correct |
60 ms |
18148 KB |
Output is correct |
30 |
Correct |
60 ms |
18100 KB |
Output is correct |
31 |
Correct |
64 ms |
18064 KB |
Output is correct |