#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (500005)
ll V;
vector<pair<ll,ll> > v[MAXN];
ll parent[20][MAXN];
ll depth[MAXN];
ll dist[MAXN];
ll visited[MAXN];
void distdfs(ll x){
visited[x] = 1;
for(auto u : v[x]){
if(visited[u.first] == 0){
dist[u.first] = dist[x] + u.second;
visited[u.first] = 1;
distdfs(u.first);
}
}
}
void dfs(ll x,ll nodeparent,ll nodedepth){
parent[0][x] = nodeparent;
depth[x] = nodedepth;
for(ll i = 0;i < v[x].size();i++){
if(v[x][i].first != nodeparent){
dfs(v[x][i].first,x,nodedepth + 1);
}
}
}
void lcainit(){
for(ll i = 1;i < 20;i++){
for(ll j = 0;j < V;j++){
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
}
long long lca(ll u,ll v){
if(depth[u] > depth[v]){
swap(u,v);
}
ll diff = depth[v] - depth[u];
for(ll i = 0;i < 20;i++){
if(diff & (1<<i)){
v = parent[i][v];
}
}
if(u == v){
return dist[u];
}
for(ll i = 19;i >= 0;i--){
if(parent[i][u] != parent[i][v]){
u = parent[i][u];
v = parent[i][v];
}
}
return dist[parent[0][u]];
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>V;
for(ll i = 0;i < (V - 1);i++){
ll a,b,w;
cin>>a>>b>>w;
v[a].push_back(make_pair(b,w));
v[b].push_back(make_pair(a,w));
}
dist[0] = 0;
visited[0] = 1;
distdfs(0);
dfs(0,0,0);
lcainit();
ll Q;
cin>>Q;
for(ll i = 0;i < Q;i++){
ll arr[5];
for(ll i = 0;i < 5;i++){
cin>>arr[i];
}
ll p[5];
memset(p,-1,sizeof(p));
for(ll j = 0;j < 5;j++){
for(ll z = 0;z < 20;z++){
if(parent[z][arr[j]] == arr[0]){
p[j] = arr[0];
break;
}else if(parent[z][arr[j]] == arr[1]){
p[j] = arr[1];
break;
}else if(parent[z][arr[j]] == arr[2]){
p[j] = arr[2];
break;
}else if(parent[z][arr[j]] == arr[3]){
p[j] = arr[3];
break;
}else if(parent[z][arr[j]] == arr[4]){
p[j] = arr[4];
break;
}
}
if(p[j] == arr[j]){
p[j] = -1; //no parent that is in arr
}
//cout<<"PARENT OF "<<arr[j]<<" which is also among arr is "<<p[j]<<'\n';
}
ll sum = 0;
for(ll i = 0;i < 5;i++){
for(ll j = 0;j < 5;j++){
if(arr[i] != arr[j]){
if(p[i] == arr[j]){
ll a = lca(arr[i],arr[j]);
sum += ((dist[arr[i]] + dist[arr[j]]) - (2 * a));
}else if(p[i] == -1 && p[j] == -1 && i > j){
//p[i] = MAXN + 5;
//p[j] = MAXN + 5;
ll a = lca(arr[i],arr[j]);
sum += ((dist[arr[i]] + dist[arr[j]]) - (2 * a));
}
}
}
}
cout<<sum<<'\n';
}
}
Compilation message
roadsideadverts.cpp: In function 'void dfs(ll, ll, ll)':
roadsideadverts.cpp:24:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(ll i = 0;i < v[x].size();i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
26280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
24544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12172 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
26280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
