#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MOD = 1e9 + 7;
const int N = 50003 + 2;
vector<pair<int, int> > graph[N];
vector<pair<long long int, pair<int, int> > > edges;
long long dis[N], lvl[N], dp[N][(int) log2(N) + 2], component[N];
void dfs(int source, int par, int level, long long int cost){
dp[source][0] = par;
lvl[source] = level;
dis[source] = cost;
for(auto k : graph[source])
if(k.first != par)
dfs(k.first, source, level + 1, cost + k.second);
}
void init(int n){
dfs(0, -1, 1, 0);
for(int i = 1; i <= log2(n); ++i)
for(int j = 0; j < n; ++j)
if(dp[j][i - 1] != -1)
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
int LCA(int u, int v, int n){
if(lvl[u] > lvl[v])
swap(u, v);
int d = lvl[v] - lvl[u];
while(d){
int jump = log2(d);
v = dp[v][jump];
d -= (1LL << jump);
}
if(v == u)
return v;
for(int i = log2(n); i >= 0; --i){
if(dp[v][i] != -1 and dp[v][i] != dp[u][i]){
v = dp[v][i];
u = dp[u][i];
}
}
return dp[v][0];
}
int find(int a){
while(1){
if(a == component[a])
return a;
component[a] = component[component[a]];
a = component[a];
}
}
void merge(int a, int b){
int u = find(a), v = find(b);
component[u] = v;
}
long long MST(){
long long ans = 0;
for(int i = 0; i < edges.size(); ++i){
int u = edges[i].second.first, v = edges[i].second.second, c = edges[i].first;
if(find(u) == find(v))
continue;
ans += c;
merge(u, v);
}
return ans;
}
void solve() {
int n;
cin >> n;
for(int i = 1; i <= n - 1; ++i){
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
for(int i = 1; i <= n; ++i)
component[i] = i;
memset(dp, -1, sizeof dp);
init(n);
int q;
cin >> q;
while(q--){
int a[5];
for(int i = 0; i < 5; ++i)
cin >> a[i];
set<int> s;
for(int i = 0; i < 5; ++i){
for(int j = i + 1; j < 5; ++j){
int p = LCA(a[i], a[j], n);
s.insert(p);
}
s.insert(a[i]);
}
vector<int> nodes;
for(auto k : s)
nodes.push_back(k);
for(int i = 0; i < nodes.size(); ++i){
for(int j = i + 1; j < nodes.size(); ++j){
int p = LCA(nodes[i], nodes[j], n);
long long int cost = dis[nodes[i]] + dis[nodes[j]] - 2 * dis[p];
edges.push_back({cost, {nodes[i], nodes[j]}});
}
}
sort(edges.begin(), edges.end());
cout << MST() << "\n";
edges.clear();
}
}
int main() {
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
Compilation message
roadsideadverts.cpp: In function 'long long int MST()':
roadsideadverts.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0; i < edges.size(); ++i){
| ~~^~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 0; i < nodes.size(); ++i){
| ~~^~~~~~~~~~~~~~
roadsideadverts.cpp:104:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j = i + 1; j < nodes.size(); ++j){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
12532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
11084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 2 |
Incorrect |
145 ms |
12532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
