#include <bits/stdc++.h>
using namespace std;
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 2;
int n;
vector<int> is_on;
vector<pair<int, int>> order_edges;
struct SEGTREE {
int tree[4 * N];
SEGTREE() {
for (int i = 0; i < 4 * N; i++) tree[i] = 0;
}
void update(int node, int l, int r, int ind) {
if (l == r) {
tree[node] ^= 1;
return;
}
int mid = (l + r) >> 1;
if (ind <= mid) update(node << 1, l, mid, ind);
else update(node << 1 | 1, mid + 1, r, ind);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
int query(int node, int l, int r, int i, int j) {
if (r < i || j < l) return 0;
if (i <= l && r <= j) return tree[node];
int mid = (l + r) >> 1;
return query(node << 1, l, mid, i, j) + query(node << 1 | 1, mid + 1, r, i, j);
}
void update(int ind) {update(1, 1, n, ind);}
int query(int i, int j) {query(1, 1, n, i, j);}
} segtree;
struct HLD {
int c_ind = 1, hn[N], p[N], t[N], ind[N], sz[N], old[N], ind_nd[N], ans[N];
vector<int> edges[N];
void init() {
sz[0] = 0;
comp_hn(1, 0);
do_hld(1, 0, 1);
for (int i = 0; i < N; i++) old[i] = 0, ans[i] = 1;
}
void add_edge(int &x, int &y) {
edges[x].push_back(y);
edges[y].push_back(x);
}
void comp_hn(int node, int parent) {
int c_hn = 0;
p[node] = parent;
sz[node] = 1;
for (int child : edges[node]) {
if (child == parent) continue;
comp_hn(child, node);
if (sz[child] > sz[c_hn]) c_hn = child;
}
hn[node] = c_hn;
}
void do_hld(int node, int parent, int top) {
t[node] = top;
ind[node] = c_ind;
ind_nd[c_ind++] = node;
if (hn[node]) do_hld(hn[node], node, top);
for (int child : edges[node]) {
if (child == parent || child == hn[node]) continue;
do_hld(child, node, child);
}
}
int lca_cc(int u) {
int l, r, v, mid;
while (p[u]) {
if (!segtree.query(ind[u], ind[u])) return u;
v = t[u];
l = ind[v] + 1, r = ind[u];
if (r >= l) {
if (segtree.query(l, r) != r - l + 1) {
while (r - l > 1) {
mid = (l + r) / 2;
if (segtree.query(mid, r) == r - mid + 1) r = mid;
else l = mid;
}
return ind_nd[r - 1];
}
}
if (!segtree.query(ind[v], ind[v])) return v;
u = p[t[u]];
}
return u;
}
void query(int x) {
int u, v, lca;
u = order_edges[x].first;
v = order_edges[x].second;
if (v == p[u]) swap(u, v), order_edges[x] = make_pair(u, v);
if (is_on[x]) {
lca = lca_cc(v);
ans[v] = old[v] = ans[lca];
segtree.update(ind[v]);
} else {
segtree.update(ind[v]);
lca = lca_cc(v);
ans[lca] += ans[v] - old[v];
}
is_on[x] ^= 1;
}
void find_ans(int node) {
cout << ans[lca_cc(node)] << "\n";
}
} hld;
void solve() {
int m, q, x, y;
cin >> n >> m >> q;
for (int i = 0; i < n - 1; i++) {
cin >> x >> y;
hld.add_edge(x, y);
order_edges.push_back(make_pair(x, y));
is_on.push_back(0);
}
hld.init();
while (m--) {
cin >> x;
x--;
hld.query(x);
}
while(q--) {
cin >> x;
hld.find_ans(x);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
ll t;
t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
Compilation message
synchronization.cpp: In member function 'int SEGTREE::query(int, int)':
synchronization.cpp:39:51: warning: no return statement in function returning non-void [-Wreturn-type]
39 | int query(int i, int j) {query(1, 1, n, i, j);}
| ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:151:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | freopen("input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:152:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen("output.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
14680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
14680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
14684 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
