#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 12, lg = 21;
int n, st, en, h[maxn], pe[maxn], par[maxn][lg], kn[maxn], U[maxn], V[maxn];
vector <int> k[maxn], conn[maxn];
vector <int> pos, path, p1, p2, qe, d;
bitset <maxn> marked;
void dfs_set(int u){
marked[u] = 1;
for(int i = 0; i + 1 < lg; i++)
par[u][i + 1] = par[par[u][i]][i];
for(int e: conn[u]){
int v = u ^ U[e] ^ V[e];
// cout << v << endl;
if(!marked[v]){
// cout << u << "->" << v << endl;
h[v] = h[u] + 1;
par[v][0] = u;
pe[v] = e;
dfs_set(v);
}
}
}
int kpar(int u, int k){
for(int i = 0; i < k; i++)
if((k >> i) & 1)
u = par[u][i];
return u;
}
int lca(int a, int b){
if(h[a] < h[b])
swap(a, b);
a = kpar(a, h[a] - h[b]);
if(a == b)
return a;
for(int i = lg - 1; i >= 0; i--)
if(par[a][i] != par[b][i]){
a = par[a][i];
b = par[b][i];
}
return par[a][0];
}
pair<int, int> get_path(int a, int b){
int x = lca(a, b);
// cout << a << ' ' << b << ' ' << x << endl;
int res = 0;
p1.clear();
p2.clear();
while(a != x){
int e = pe[a];
int v = par[a][0];
p1.push_back(e);
a = v;
//cout << a << endl;
}
while(b != x){
int e = pe[b];
int v = par[b][0];
p2.push_back(e);
b = v;
}
reverse(p2.begin(), p2.end());
for(int i = 0; i < p2.size(); i++)
p1.push_back(p2[i]);
int now = st;
for(int i: p1){
// cout << now << '-' << endl;
if(kn[i] != 0){
// cout << i << "n" << endl;
d.push_back(now);
return make_pair(kn[i], i);
}
now = now ^ U[i] ^ V[i];
}
return make_pair(0, p1.size());
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n;
cin >> st >> en;
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b >> kn[i];
conn[a].push_back(i);
conn[b].push_back(i);
U[i] = a;
V[i] = b;
}
dfs_set(1);
// return 0;
pos.push_back(en);
int ans = 0;
int cnt = 0;
while(pos.size()){
cnt += 1;
if(cnt > 50)
return 0;
int x = pos.back();
/* for(int j: pos)
cout << j << ' ';
cout << endl;
for(int j: d)
cout << j << ' ';
cout << endl;
cout << st << "->" << x << endl;
cout << ans << endl;
cout << endl;
cout << endl;*/
auto res = get_path(st, x);
if(res.first != 0){
qe.push_back(res.second);
pos.push_back(res.first);
continue;
}
ans += res.second;
if(d.size()){
ans += get_path(x, d.back()).second;
st = d.back();
d.pop_back();
}
if(qe.size()){
// cout << qe.back() << '-' << endl;
kn[qe.back()] = 0;
qe.pop_back();
}
pos.pop_back();
}
cout << ans << endl;
}
Compilation message
Main.cpp: In function 'std::pair<int, int> get_path(int, int)':
Main.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < p2.size(); i++)
| ~~^~~~~~~~~~~
Main.cpp:50:9: warning: unused variable 'res' [-Wunused-variable]
50 | int res = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
47220 KB |
Output is correct |
| 2 |
Correct |
20 ms |
47300 KB |
Output is correct |
| 3 |
Incorrect |
76 ms |
62164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
47260 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47268 KB |
Output is correct |
| 3 |
Incorrect |
27 ms |
47300 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
47220 KB |
Output is correct |
| 2 |
Correct |
20 ms |
47300 KB |
Output is correct |
| 3 |
Incorrect |
76 ms |
62164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
