#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 5e4+11;
vector<pair<int,int>> adj[MAXN];
int tin[MAXN], tout[MAXN], par[MAXN][20], dep[MAXN], dist[MAXN];
int timer;
void dfs(int u, int p){
tin[u] = ++timer;
for(auto c : adj[u]){
if(c.f != p){
dep[c.f] = dep[u]+1; par[c.f][0] = u; dist[c.f] = dist[u]+c.s;
for(int i = 1;i<20;++i) par[c.f][i] = par[par[c.f][i-1]][i-1];
dfs(c.f,u);
}
}
tout[u] = timer;
}
int calcanc(int u, int k){
for(int i = 19;i>=0;--i){
if(k >= (1<<i)){
u = par[u][i];
k -= (1<<i);
}
}
return u;
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u,v);
u = calcanc(u,dep[u]-dep[v]);
for(int i = 19;i>=0;--i){
if(par[u][i] != par[v][i]){
u = par[u][i]; v = par[v][i];
}
}
return (u == v) ? u : par[u][0];
}
bool checkanc(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
bool cmp(int x, int y){
return tin[x] < tin[y];
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N; cin >> N;
for(int i = 0;i<N-1;++i){
int u,v,w; cin >> u >> v >> w;
adj[u].push_back({v,w}); adj[v].push_back({u,w});
}
dfs(0,-1);
int Q; cin >> Q;
while(Q--){
vector<int> q(5);
for(int i = 0;i<5;++i) cin >> q[i];
sort(q.begin(),q.end(),cmp);
vector<int> path; path.push_back(q[0]);
int ans = 0;
for(int i = 0;i<5;++i){
while(path.size() >= 2 && checkanc(lca(path.back(),q[i]), path[path.size()-2])){
ans += dist[path.back()]-dist[path[path.size()-2]];
//cout << path.back() << " " << path[path.size()-2] << " " << dist[path.back()]-dist[path[path.size()-2]] << "\n";
path.pop_back();
}
if(checkanc(path.back(),q[i])){
path.push_back(q[i]);
}
else{
int a = lca(path.back(),q[i]);
ans += dist[path.back()]-dist[a];
path.pop_back();
path.push_back(a);
path.push_back(q[i]);
}
}
while(path.size() >= 2){
ans += dist[path.back()]-dist[path[path.size()-2]];
path.pop_back();
}
cout << ans << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
9552 KB |
Output is correct |
2 |
Correct |
42 ms |
12112 KB |
Output is correct |
3 |
Correct |
40 ms |
12112 KB |
Output is correct |
4 |
Correct |
45 ms |
12112 KB |
Output is correct |
5 |
Correct |
42 ms |
12112 KB |
Output is correct |
6 |
Correct |
40 ms |
12112 KB |
Output is correct |
7 |
Correct |
37 ms |
12116 KB |
Output is correct |
8 |
Correct |
38 ms |
12112 KB |
Output is correct |
9 |
Correct |
45 ms |
12112 KB |
Output is correct |
10 |
Correct |
45 ms |
12384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
8024 KB |
Output is correct |
2 |
Correct |
24 ms |
11276 KB |
Output is correct |
3 |
Correct |
27 ms |
11088 KB |
Output is correct |
4 |
Correct |
30 ms |
11220 KB |
Output is correct |
5 |
Correct |
25 ms |
11096 KB |
Output is correct |
6 |
Correct |
24 ms |
11232 KB |
Output is correct |
7 |
Correct |
26 ms |
11088 KB |
Output is correct |
8 |
Correct |
25 ms |
11088 KB |
Output is correct |
9 |
Correct |
24 ms |
11096 KB |
Output is correct |
10 |
Correct |
24 ms |
11096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1624 KB |
Output is correct |
2 |
Correct |
43 ms |
9552 KB |
Output is correct |
3 |
Correct |
42 ms |
12112 KB |
Output is correct |
4 |
Correct |
40 ms |
12112 KB |
Output is correct |
5 |
Correct |
45 ms |
12112 KB |
Output is correct |
6 |
Correct |
42 ms |
12112 KB |
Output is correct |
7 |
Correct |
40 ms |
12112 KB |
Output is correct |
8 |
Correct |
37 ms |
12116 KB |
Output is correct |
9 |
Correct |
38 ms |
12112 KB |
Output is correct |
10 |
Correct |
45 ms |
12112 KB |
Output is correct |
11 |
Correct |
45 ms |
12384 KB |
Output is correct |
12 |
Correct |
19 ms |
8024 KB |
Output is correct |
13 |
Correct |
24 ms |
11276 KB |
Output is correct |
14 |
Correct |
27 ms |
11088 KB |
Output is correct |
15 |
Correct |
30 ms |
11220 KB |
Output is correct |
16 |
Correct |
25 ms |
11096 KB |
Output is correct |
17 |
Correct |
24 ms |
11232 KB |
Output is correct |
18 |
Correct |
26 ms |
11088 KB |
Output is correct |
19 |
Correct |
25 ms |
11088 KB |
Output is correct |
20 |
Correct |
24 ms |
11096 KB |
Output is correct |
21 |
Correct |
24 ms |
11096 KB |
Output is correct |
22 |
Correct |
48 ms |
10576 KB |
Output is correct |
23 |
Correct |
36 ms |
9256 KB |
Output is correct |
24 |
Correct |
41 ms |
11600 KB |
Output is correct |
25 |
Correct |
44 ms |
11600 KB |
Output is correct |
26 |
Correct |
42 ms |
11600 KB |
Output is correct |
27 |
Correct |
41 ms |
11648 KB |
Output is correct |
28 |
Correct |
43 ms |
11600 KB |
Output is correct |
29 |
Correct |
41 ms |
11540 KB |
Output is correct |
30 |
Correct |
40 ms |
11600 KB |
Output is correct |
31 |
Correct |
45 ms |
11600 KB |
Output is correct |