#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
struct AIB {
int n;
vector<int> aib;
AIB(int N) : n(N), aib(N + 1, 0) {}
void update(int x, int val) {
for(int i = x; i <= n; i += i & -i)
aib[i] += val;
}
int query(int x) {
int sum = 0;
for(int i = x; i >= 1; i -= i & -i)
sum += aib[i];
return sum;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
};
struct tree {
const int LOG = 20;
vector<vector<int>> L;
vector<vector<int>> Anc;
vector<int> parent, level, l, r;
AIB fen;
int n;
tree(int N) : n(N), L(N), fen(N), parent(N, 0), level(N, 0), l(N), r(N) {}
void add_edge(int x, int y) {
L[x].push_back(y);
L[y].push_back(x);
}
void init() {
int t = 0;
function<void(int, int)> dfs = [&](int u, int par) {
parent[u] = par;
l[u] = ++t;
for(auto v : L[u]) {
if(v != par) {
level[v] = level[u] + 1;
dfs(v, u);
}
}
r[u] = t;
};
dfs(1, 0);
Anc.push_back(parent);
for(int k = 1; k < LOG; ++k) {
Anc.push_back(vector<int>(n, 0));
for(int i = 1; i < n; ++i)
Anc[k][i] = Anc[k - 1][Anc[k - 1][i]];
}
// for(int i = 1; i < n; ++i) {
// for(int k = 0; k <= 2; ++k)
// cout << Anc[k][i] << " ";
// cout << "\n";
// }
}
int lift(int a, int x) {
for(int k = 0; k < LOG; k++)
if(x & (1 << k))
a = Anc[k][a];
return a;
}
int lca(int a, int b) {
if(level[a] < level[b])
swap(a, b);
a = lift(a, level[b] - level[a]);
for(int k = LOG - 1; k >= 0; k--) {
if(Anc[k][a] != Anc[k][b]) {
a = Anc[k][a];
b = Anc[k][b];
}
}
return Anc[0][a];
}
void upd(int u) {
fen.update(l[u], +1);
fen.update(r[u] + 1, -1);
}
int go_up(int u) {
for(int i = LOG - 1; i >= 0; --i) {
int x = Anc[i][u];
if(fen.query(l[x] + 1, l[u]) == level[u] - level[x])
u = Anc[i][u];
}
return u;
}
};
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, m, q;
cin >> n >> m >> q;
tree T(n + 1);
vector<pair<int, int>> edge;
for(int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
edge.push_back({x, y});
T.add_edge(x, y);
}
T.init();
vector<int> cnt(n + 1, 1), cnt2(n + 1, 0);
vector<int> active(n, 0);
while(m--) {
int i;
cin >> i;
--i;
int x = edge[i].first, y = edge[i].second;
if(T.level[x] > T.level[y]) swap(x, y);
x = T.go_up(x);
if(!active[i]) {
cnt[x] += cnt[y] - cnt2[y];
T.upd(y);
} else {
T.upd(y);
cnt[y] = cnt2[y] = cnt[x];
}
active[i] ^= 1;
}
while(q--) {
int x;
cin >> x;
x = T.go_up(x);
cout << cnt[x] << "\n";
}
return 0;
}
Compilation message
synchronization.cpp: In constructor 'tree::tree(int)':
synchronization.cpp:47:9: warning: 'tree::n' will be initialized after [-Wreorder]
47 | int n;
| ^
synchronization.cpp:43:25: warning: 'std::vector<std::vector<int> > tree::L' [-Wreorder]
43 | vector<vector<int>> L;
| ^
synchronization.cpp:49:5: warning: when initialized here [-Wreorder]
49 | tree(int N) : n(N), L(N), fen(N), parent(N, 0), level(N, 0), l(N), r(N) {}
| ^~~~
synchronization.cpp:46:9: warning: 'tree::fen' will be initialized after [-Wreorder]
46 | AIB fen;
| ^~~
synchronization.cpp:45:17: warning: 'std::vector<int> tree::parent' [-Wreorder]
45 | vector<int> parent, level, l, r;
| ^~~~~~
synchronization.cpp:49:5: warning: when initialized here [-Wreorder]
49 | tree(int N) : n(N), L(N), fen(N), parent(N, 0), level(N, 0), l(N), r(N) {}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
24696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
352 ms |
30124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
