#include <iostream>
#include <vector>
#define pii pair<int,int>
#define mkp make_pair
#define fst first
#define snd second
#define vpi vector<pii>
#define epb emplace_back
using namespace std;
vector<vpi> adj;vector<int> tmp;
int v,sp[2][50001][20]={},q,h[50001]={},tplca,tplgth,tpa,tpb;
void dfs(int u,int p,int pw,int ht)
{
sp[0][u][0] = p;sp[1][u][0] = pw;h[u] = ht;
for (int i=1;i<20;i++)
{
if (sp[0][u][i-1]!=-1)
{
sp[0][u][i] = sp[0][sp[0][u][i-1]][i-1];
sp[1][u][i] = sp[1][u][i-1] + sp[1][sp[0][u][i-1]][i-1];
}
else {break;}
}
for (auto v:adj[u])
{
if (v.fst!=p)
{
dfs(v.fst,u,v.snd,ht+1);
}
}
}
pii lca(int a,int b)
{
int diff, ptr = 0,crl = 0;
if (h[a]>h[b]) {swap(a,b);}
diff = h[b]-h[a];
while (diff)
{
if (diff%2)
{
crl += sp[1][b][ptr];
b = sp[0][b][ptr];
}
ptr++;diff=diff>>1;
}
while (a!=b)
{
for (int j=19;j>=0;j--)
{
if (sp[0][b][j] != sp[0][a][j])
{
crl += sp[1][a][j]; crl+=sp[1][b][j];
a = sp[0][a][j]; b = sp[0][b][j];
}
else if (j==0)
{
crl+=sp[1][a][0]; crl+=sp[1][b][0];
a = sp[0][a][0]; b = a;
}
}
}
return mkp(a,crl);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>v;
for (int i=0;i<v;i++)
{
adj.epb(vpi());
for (int j=0;j<20;j++)
{
sp[0][i][j]=-1;
sp[1][i][j]=0;
}
}
for (int i=0;i<v-1;i++)
{
int a,b,c;cin>>a>>b>>c;
adj[a].epb(b,c);
adj[b].epb(a,c);
}
dfs(0,-1,0,0);
cin>>q;
for (int i=0;i<q;i++)
{
int rslt = 0;
for (int j=0;j<5;j++) {int a;cin>>a;tmp.epb(a);}
for (int l=4;l;l--)
{
tplca = -1;vector<int> tmp2;
for (int j=0;j<=l;j++)
{
for (int k=j+1;k<=l;k++)
{
pii rslt = lca(tmp[j],tmp[k]);
//cout<<j<<" "<<k<<" "<<rslt.fst<<" "<<rslt.snd<<"\n";
if (tplca==-1) {tplca = rslt.fst; tplgth = rslt.snd; tpa=j;tpb = k;}
else if (h[rslt.fst]>h[tplca]) {tplca = rslt.fst; tplgth = rslt.snd; tpa=j;tpb = k;}
}
}
for (int j=0;j<=l;j++)
{
if (j!=tpa&&j!=tpb) {tmp2.epb(tmp[j]);}
}
tmp2.epb(tplca);
tmp=tmp2;
//for (int i=0;i<l;i++) {cout<<tmp[i]<<" ";}cout<<" "<<tpa<<" "<<tpb<<"\n";
rslt+=tplgth;
}
cout<<rslt<<"\n";
tmp.clear();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
170 ms |
13544 KB |
Output is correct |
2 |
Correct |
124 ms |
14632 KB |
Output is correct |
3 |
Correct |
122 ms |
14572 KB |
Output is correct |
4 |
Correct |
138 ms |
14584 KB |
Output is correct |
5 |
Correct |
121 ms |
14632 KB |
Output is correct |
6 |
Correct |
123 ms |
14568 KB |
Output is correct |
7 |
Correct |
119 ms |
14572 KB |
Output is correct |
8 |
Correct |
120 ms |
14576 KB |
Output is correct |
9 |
Correct |
113 ms |
14640 KB |
Output is correct |
10 |
Correct |
119 ms |
14568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
12148 KB |
Output is correct |
2 |
Correct |
56 ms |
13928 KB |
Output is correct |
3 |
Correct |
60 ms |
13928 KB |
Output is correct |
4 |
Correct |
65 ms |
13928 KB |
Output is correct |
5 |
Correct |
60 ms |
13872 KB |
Output is correct |
6 |
Correct |
58 ms |
14060 KB |
Output is correct |
7 |
Correct |
62 ms |
13928 KB |
Output is correct |
8 |
Correct |
57 ms |
13932 KB |
Output is correct |
9 |
Correct |
59 ms |
13928 KB |
Output is correct |
10 |
Correct |
61 ms |
13928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
170 ms |
13544 KB |
Output is correct |
3 |
Correct |
124 ms |
14632 KB |
Output is correct |
4 |
Correct |
122 ms |
14572 KB |
Output is correct |
5 |
Correct |
138 ms |
14584 KB |
Output is correct |
6 |
Correct |
121 ms |
14632 KB |
Output is correct |
7 |
Correct |
123 ms |
14568 KB |
Output is correct |
8 |
Correct |
119 ms |
14572 KB |
Output is correct |
9 |
Correct |
120 ms |
14576 KB |
Output is correct |
10 |
Correct |
113 ms |
14640 KB |
Output is correct |
11 |
Correct |
119 ms |
14568 KB |
Output is correct |
12 |
Correct |
36 ms |
12148 KB |
Output is correct |
13 |
Correct |
56 ms |
13928 KB |
Output is correct |
14 |
Correct |
60 ms |
13928 KB |
Output is correct |
15 |
Correct |
65 ms |
13928 KB |
Output is correct |
16 |
Correct |
60 ms |
13872 KB |
Output is correct |
17 |
Correct |
58 ms |
14060 KB |
Output is correct |
18 |
Correct |
62 ms |
13928 KB |
Output is correct |
19 |
Correct |
57 ms |
13932 KB |
Output is correct |
20 |
Correct |
59 ms |
13928 KB |
Output is correct |
21 |
Correct |
61 ms |
13928 KB |
Output is correct |
22 |
Correct |
136 ms |
13456 KB |
Output is correct |
23 |
Correct |
79 ms |
12652 KB |
Output is correct |
24 |
Correct |
115 ms |
14312 KB |
Output is correct |
25 |
Correct |
123 ms |
14312 KB |
Output is correct |
26 |
Correct |
124 ms |
14216 KB |
Output is correct |
27 |
Correct |
116 ms |
14312 KB |
Output is correct |
28 |
Correct |
116 ms |
14316 KB |
Output is correct |
29 |
Correct |
117 ms |
14316 KB |
Output is correct |
30 |
Correct |
119 ms |
14316 KB |
Output is correct |
31 |
Correct |
115 ms |
14312 KB |
Output is correct |