#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX=5e4, LGMAX=16;
vector <pair <int, int>> vec[NMAX+5];
int n;
int t[NMAX+5][LGMAX+1], sum[NMAX+5][LGMAX+1], v[10], depth[NMAX+5];
void dfs (int nod, int tatal=0, int w=0)
{
t[nod][0]=tatal;
depth[nod]=depth[tatal]+1;
sum[nod][0]=w;
for (int i=1;i<=LGMAX;i++)
{
t[nod][i]=t[t[nod][i-1]][i-1];
sum[nod][i]=sum[nod][i-1]+sum[t[nod][i-1]][i-1];
}
for (auto adj : vec[nod])
{
if (adj.first==tatal)
continue;
dfs (adj.first, nod, adj.second);
}
}
pair <int, int> LCA (int x, int y)
{
if (x==y)
return {x, 0};
int cost=0;
if (depth[x]>depth[y])
swap (x, y);
for (int i=LGMAX;i>=0;i--)
if (t[y][i]!=0 && depth[t[y][i]]>=depth[x])
cost+=sum[y][i], y=t[y][i];
if (x==y)
return {x, cost};
for (int i=LGMAX;i>=0;i--)
if (t[y][i]!=0 && t[y][i]!=t[x][i])
cost+=sum[x][i], cost+=sum[y][i], x=t[x][i], y=t[y][i];
return {t[x][0], cost+t[x][0]+t[y][0]};
}
int32_t main ()
{
ios_base :: sync_with_stdio (0);
cin.tie (nullptr);
cin >> n;
for (int i=1;i<n;i++)
{
int x, y, w;
cin >> x >> y >> w;
x++;
y++;
vec[x].push_back ({y, w});
vec[y].push_back ({x, w});
}
dfs (1);
int q;
cin >> q;
while (q--)
{
int glob_lca=0;
for (int i=0;i<5;i++)
{
cin >> v[i];
v[i]++;
if (i==1)
glob_lca=v[i];
else
glob_lca=LCA (v[i], glob_lca).first;
}
int cost=0;
for (int msk=0;msk<(1 << 5);msk++)
{
int crt_lca=0;
for (int i=0;i<5;i++)
{
if (msk & (1 << i))
crt_lca=(crt_lca==0?v[i]:LCA (crt_lca, v[i]).first);
}
cost+=LCA (crt_lca, glob_lca).second*(__builtin_popcount (msk)%2==0?-1:1);
}
cout << cost << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |