#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, l;
const int N = (int)1e5+5;
vector<int> graph[N], gdist[N], d(N), tin, tout;
int timer;
vector<vector<int>> up;
void dfs(int v, int p){
tin[v] = ++timer;
up[v][0] = p;
for(int i = 1; i <= l; i++){
up[v][i] = up[up[v][i-1]][i-1];
}
for(int i = 0; i < gdist[v].size(); i++){
int loc = graph[v][i];
if(loc==p) continue;
d[loc]=d[v]+gdist[v][i];
dfs(loc,v);
}
tout[v] = ++timer;
}
bool is_ancestor(int u, int v){
return tin[u]<=tin[v] and tout[u]>=tout[v];
}
int lca(int u, int v){
if(is_ancestor(u,v)) return u;
if(is_ancestor(v,u)) return v;
for(int i = l; i >= 0; --i){
if(!is_ancestor(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
bool fun(int x, int y){
return tin[x] < tin[y];
}
int dist(int x, int y){
return d[x] + d[y] - 2 * d[lca(x, y)];
}
int main(){
ios_base::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
cin >> n;
for(int i = 0; i < n-1; i++){
int x,y,d; cin>>x>>y>>d;
graph[x].emplace_back(y);
graph[y].push_back(x);
gdist[x].emplace_back(d);
gdist[y].push_back(d);
}
//preprocess
tin.resize(n);
tout.resize(n);
timer = 0;
l = ceil(log2(n));
up.assign(n, vector<int>(l+1));
dfs(0,0);
int quer;
cin>>quer;
while(quer--){
vector<int> q(5);
for(int& i: q) cin >> i;
sort(q.begin(), q.end(), fun);
int ans = 0;
ans += dist(q[0], lca(0, q[0]));
for(int i = 1; i < 5; i++){
ans += dist(lca(q[i-1],q[i]), q[i]);
}
//ans += 50;
cout << ans << '\n';
}
}
Compilation message
roadsideadverts.cpp: In function 'void dfs(int, int)':
roadsideadverts.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i = 0; i < gdist[v].size(); i++){
| ~~^~~~~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
49 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10860 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
10860 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10860 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10860 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
