#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
#define ff first
#define ss second
const ll mod = 1000000007;
const ll maxn = 50005;
ll n,sz,tim=0,cnt=0;
vector<pl> adj[maxn];
ll up[maxn][20];
ll tin[maxn];
ll tout[maxn];
ll order[maxn];
ll depth[maxn];
void dfs(ll i, ll pa){
order[i]=cnt++;
tin[i]=tim++;
up[i][0]=pa;
forp(j,1,sz){
up[i][j]=up[up[i][j-1]][j-1];
}
for(auto u:adj[i]){
if(u.ff!=pa){
depth[u.ff]=depth[i]+u.ss;
dfs(u.ff,i);
}
}
tout[i]=tim++;
}
bool is_anc(ll u, ll v){
return (tin[v]<=tin[u] && tout[u]<=tout[v]);
}
ll lca(ll u, ll v){
if(is_anc(u,v)){
return v;
}
if(is_anc(v,u)){
return u;
}
forn(i,sz,0){
if(!is_anc(v,up[u][i])){
u=up[u][i];
}
}
return up[u][0];
}
void solve(){
cin>>n; sz=ceil(log2(n));
forp(i,1,n-1){
ll u,v,w; cin>>u>>v>>w; u++;v++;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
dfs(1,1);
ll q; cin>>q;
forp(i,1,q){
ll a[5];
forp(j,0,4){
cin>>a[j]; a[j]++;
}
sort(a,a+4,[](ll u, ll v){
return order[u]<order[v];
});
ll sum=0;
forp(j,0,4){
sum+=(depth[a[j]]+depth[a[(j+1)%5]]-2*depth[lca(a[j],a[(j+1)%5])]);
}
cout<<sum/2<<newl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1; //cin>>t;
while(t--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
14440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
13432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
14440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
