#include <bits/stdc++.h>
using namespace std;
const int nx=5e4+5, lx=17;
int n, u, v, w, pa[nx][lx], lvl[nx], ds[nx], l[6], q, tn;
vector<vector<pair<int, int>>> d(nx);
void dfs(int u, int p)
{
lvl[u]=lvl[p]+1;
pa[u][0]=p;
for (int i=1; i<lx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
for (auto [v, w]:d[u]) if (v!=p) ds[v]=ds[u]+w, dfs(v, u);
}
int lca(int u, int v)
{
if (lvl[u]>lvl[v]) swap(u, v);
for (int i=lx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
if (u==v) return v;
for (int i=lx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
return pa[u][0];
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n; lvl[n]=1e9;
for (int i=0; i<n-1; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
dfs(0, 0);
cin>>q;
while (q--)
{
for (int i=0; i<5; i++) cin>>l[i];
int tn=n, ans=0;
for (int i=1; i<5; i++)
{
int cn=lca(l[0], l[i]);
if (lvl[cn]<lvl[tn]) tn=cn;
}
for (int i=0; i<5; i++)
{
int mn=ds[l[i]]-ds[tn];
for (int j=0; j<i; j++) mn=min(mn, ds[l[i]]-ds[lca(l[i], l[j])]);
ans+=mn;
}
cout<<ans<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
9512 KB |
Output is correct |
2 |
Correct |
66 ms |
11112 KB |
Output is correct |
3 |
Correct |
74 ms |
11120 KB |
Output is correct |
4 |
Correct |
61 ms |
10992 KB |
Output is correct |
5 |
Correct |
66 ms |
10932 KB |
Output is correct |
6 |
Correct |
57 ms |
11020 KB |
Output is correct |
7 |
Correct |
67 ms |
10956 KB |
Output is correct |
8 |
Correct |
58 ms |
10944 KB |
Output is correct |
9 |
Correct |
58 ms |
10956 KB |
Output is correct |
10 |
Correct |
64 ms |
10916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
7772 KB |
Output is correct |
2 |
Correct |
37 ms |
10064 KB |
Output is correct |
3 |
Correct |
38 ms |
10148 KB |
Output is correct |
4 |
Correct |
50 ms |
10060 KB |
Output is correct |
5 |
Correct |
36 ms |
10060 KB |
Output is correct |
6 |
Correct |
34 ms |
10152 KB |
Output is correct |
7 |
Correct |
38 ms |
10152 KB |
Output is correct |
8 |
Correct |
30 ms |
10136 KB |
Output is correct |
9 |
Correct |
50 ms |
10084 KB |
Output is correct |
10 |
Correct |
32 ms |
10156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1492 KB |
Output is correct |
2 |
Correct |
82 ms |
9512 KB |
Output is correct |
3 |
Correct |
66 ms |
11112 KB |
Output is correct |
4 |
Correct |
74 ms |
11120 KB |
Output is correct |
5 |
Correct |
61 ms |
10992 KB |
Output is correct |
6 |
Correct |
66 ms |
10932 KB |
Output is correct |
7 |
Correct |
57 ms |
11020 KB |
Output is correct |
8 |
Correct |
67 ms |
10956 KB |
Output is correct |
9 |
Correct |
58 ms |
10944 KB |
Output is correct |
10 |
Correct |
58 ms |
10956 KB |
Output is correct |
11 |
Correct |
64 ms |
10916 KB |
Output is correct |
12 |
Correct |
31 ms |
7772 KB |
Output is correct |
13 |
Correct |
37 ms |
10064 KB |
Output is correct |
14 |
Correct |
38 ms |
10148 KB |
Output is correct |
15 |
Correct |
50 ms |
10060 KB |
Output is correct |
16 |
Correct |
36 ms |
10060 KB |
Output is correct |
17 |
Correct |
34 ms |
10152 KB |
Output is correct |
18 |
Correct |
38 ms |
10152 KB |
Output is correct |
19 |
Correct |
30 ms |
10136 KB |
Output is correct |
20 |
Correct |
50 ms |
10084 KB |
Output is correct |
21 |
Correct |
32 ms |
10156 KB |
Output is correct |
22 |
Correct |
84 ms |
9536 KB |
Output is correct |
23 |
Correct |
70 ms |
8164 KB |
Output is correct |
24 |
Correct |
63 ms |
10516 KB |
Output is correct |
25 |
Correct |
76 ms |
10456 KB |
Output is correct |
26 |
Correct |
66 ms |
10444 KB |
Output is correct |
27 |
Correct |
63 ms |
10512 KB |
Output is correct |
28 |
Correct |
67 ms |
10540 KB |
Output is correct |
29 |
Correct |
74 ms |
10504 KB |
Output is correct |
30 |
Correct |
66 ms |
10440 KB |
Output is correct |
31 |
Correct |
72 ms |
10544 KB |
Output is correct |