#include <bits/stdc++.h>
using namespace std;
#define int long long
int mini = 1e18, ans = 1;
const int mod= 1e9 + 7;
int par[20][50005], depth[50005], dist[50005];
vector<pair<int, int> > v[50005];
void dis(int p, int cost){
if(p == 0 && cost)return;
if(!dist[p])dist[p] = cost;
else return;
for(auto i : v[p])dis(i.first, cost + i.second);
}
void dfs(int x, int p, int dep){
par[0][x] = p;
depth[x] = dep;
for(auto i : v[x]){
if(i.first != p)dfs(i.first, x, dep + 1);
}
}
int lca(int a, int b){
if(depth[a] > depth[b])swap(a, b);
int diff = depth[b] - depth[a];
for(int i=0;i<=19;i++){
if(diff & (1<<i))b = par[i][b];
}
if(a == b)return a;
for(int i=19;i>=0;i--){
if(par[i][a] != par[i][b]){
a = par[i][a], b = par[i][b];
}
}
return par[0][a];
}
int p[100005];
int getr(int x){
if(p[x] == x)return x;
else return p[x] = getr(p[x]);
}
void merge(int a, int b){
a = getr(a); b = getr(b);
if(a != b)p[b] = a;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;cin >> n;
for(int i=1;i<n;i++){
int a,b,c;
cin >> a >> b >> c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
dis(0, 0);
dfs(0, -1, 1);
for(int i=1;i<=19;i++){
for(int j=0;j<n;j++)par[i][j] = par[i-1][par[i-1][j]];
}
int q;cin >> q;
while(q--){
vector<int>temp;
for(int i=0;i<5;i++){
int a;cin >> a; temp.push_back(a);
}
for(int i=0;i<5;i++){
for(int j=0;j<5;j++)temp.push_back(lca(temp[i], temp[j]));
}
sort(temp.begin(),temp.end());
temp.erase(unique(temp.begin(),temp.end()),temp.end());
vector<pair<int, pair<int, int> > >adj;
for(int i=0;i<(int)temp.size();i++){
for(int j=0;j<(int)temp.size();j++)adj.push_back({dist[temp[i]] + dist[temp[j]] - 2 * dist[lca(temp[i], temp[j])], {temp[i], temp[j]}});
}
int ans =0 ;
sort(adj.begin(), adj.end());
for(int i=0;i<(int)temp.size();i++)p[temp[i]] = temp[i];
for(auto i : adj){
int x = i.first,y =i.second.first, z= i.second.second;
if(getr(y) == getr(z))continue;
merge(y,z);
ans += x;
}
cout << ans << '\n';
}
}
Compilation message
roadsideadverts.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
44 | main(){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
187 ms |
15200 KB |
Output is correct |
2 |
Correct |
112 ms |
16484 KB |
Output is correct |
3 |
Correct |
124 ms |
16588 KB |
Output is correct |
4 |
Correct |
113 ms |
16544 KB |
Output is correct |
5 |
Correct |
123 ms |
16452 KB |
Output is correct |
6 |
Correct |
124 ms |
16596 KB |
Output is correct |
7 |
Correct |
117 ms |
16460 KB |
Output is correct |
8 |
Correct |
136 ms |
16468 KB |
Output is correct |
9 |
Correct |
115 ms |
16460 KB |
Output is correct |
10 |
Correct |
128 ms |
16480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
13764 KB |
Output is correct |
2 |
Correct |
41 ms |
15740 KB |
Output is correct |
3 |
Correct |
43 ms |
15812 KB |
Output is correct |
4 |
Correct |
34 ms |
15840 KB |
Output is correct |
5 |
Correct |
34 ms |
15856 KB |
Output is correct |
6 |
Correct |
37 ms |
15788 KB |
Output is correct |
7 |
Correct |
30 ms |
15824 KB |
Output is correct |
8 |
Correct |
32 ms |
15744 KB |
Output is correct |
9 |
Correct |
35 ms |
15820 KB |
Output is correct |
10 |
Correct |
39 ms |
15840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
2 |
Correct |
187 ms |
15200 KB |
Output is correct |
3 |
Correct |
112 ms |
16484 KB |
Output is correct |
4 |
Correct |
124 ms |
16588 KB |
Output is correct |
5 |
Correct |
113 ms |
16544 KB |
Output is correct |
6 |
Correct |
123 ms |
16452 KB |
Output is correct |
7 |
Correct |
124 ms |
16596 KB |
Output is correct |
8 |
Correct |
117 ms |
16460 KB |
Output is correct |
9 |
Correct |
136 ms |
16468 KB |
Output is correct |
10 |
Correct |
115 ms |
16460 KB |
Output is correct |
11 |
Correct |
128 ms |
16480 KB |
Output is correct |
12 |
Correct |
29 ms |
13764 KB |
Output is correct |
13 |
Correct |
41 ms |
15740 KB |
Output is correct |
14 |
Correct |
43 ms |
15812 KB |
Output is correct |
15 |
Correct |
34 ms |
15840 KB |
Output is correct |
16 |
Correct |
34 ms |
15856 KB |
Output is correct |
17 |
Correct |
37 ms |
15788 KB |
Output is correct |
18 |
Correct |
30 ms |
15824 KB |
Output is correct |
19 |
Correct |
32 ms |
15744 KB |
Output is correct |
20 |
Correct |
35 ms |
15820 KB |
Output is correct |
21 |
Correct |
39 ms |
15840 KB |
Output is correct |
22 |
Correct |
193 ms |
15208 KB |
Output is correct |
23 |
Correct |
239 ms |
14112 KB |
Output is correct |
24 |
Correct |
147 ms |
16352 KB |
Output is correct |
25 |
Correct |
174 ms |
16252 KB |
Output is correct |
26 |
Correct |
163 ms |
16224 KB |
Output is correct |
27 |
Correct |
167 ms |
16200 KB |
Output is correct |
28 |
Correct |
197 ms |
16276 KB |
Output is correct |
29 |
Correct |
141 ms |
16108 KB |
Output is correct |
30 |
Correct |
147 ms |
16188 KB |
Output is correct |
31 |
Correct |
187 ms |
16264 KB |
Output is correct |