#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
template<class T> using vt = vector<T>;
// ------------------- FW (Fenwick Tree) -----------------------
template<class T, typename F = function<T(const T&, const T&)>>
class FW {
public:
int n, N;
vt<T> root;
T DEFAULT;
F func;
FW() {}
FW(int n, T DEFAULT, F func) : func(func) {
this->n = n;
this->DEFAULT = DEFAULT;
N = floor(log2(n));
root.resize(n, DEFAULT);
}
void update_at(int id, T val) {
assert(id >= 0);
while(id < n) {
root[id] = func(root[id], val);
id |= (id + 1);
}
}
T get(int id) {
assert(id < n);
T res = DEFAULT;
while(id >= 0) {
res = func(res, root[id]);
id = (id & (id + 1)) - 1;
}
return res;
}
T queries_range(int left, int right) {
if(left > right) return DEFAULT;
return get(right) - (left - 1 >= 0 ? get(left - 1) : 0);
}
T queries_at(int i) {
return queries_range(i, i);
}
// Use r+1 to update an inclusive range [l, r]
void update_range(int l, int r, T val) {
update_at(l, val);
if(r + 1 < n)
update_at(r + 1, -val);
}
void reset() {
root.assign(n, DEFAULT);
}
int select(int x) { // get pos where prefix sum >= x
int global = get(n - 1), curr = 0;
for(int i = N; i >= 0; i--) {
int t = curr ^ (1LL << i);
if(t < n && global - root[t] >= x) {
swap(curr, t);
global -= root[curr];
}
}
return curr + 1;
}
};
// ------------------- LCA_O1 (LCA using Euler Tour & Sparse Table) -----------------------
template<typename T = int>
struct LCA_O1 {
vector<int> enter;
vpii euler;
vector<vector<pii>> st;
vector<int> log_table;
int timer;
LCA_O1() {}
LCA_O1(const vt<vt<T>> &graph, int root = 0) : timer(0) {
int n = graph.size();
enter.resize(n, -1);
dfs(root, -1, 0, graph);
int m = euler.size();
log_table.resize(m + 1);
for (int i = 2; i <= m; i++) log_table[i] = log_table[i / 2] + 1;
int K = log_table[m] + 1;
st.assign(K, vector<pii>(m));
for (int i = 0; i < m; i++) st[0][i] = euler[i];
for (int j = 1; j < K; j++) {
for (int i = 0; i + (1 << j) <= m; i++) {
pii a = st[j - 1][i], b = st[j - 1][i + (1 << (j - 1))];
st[j][i] = (a.first < b.first ? a : b);
}
}
}
void dfs(int node, int par, int d, const vt<vt<T>> &graph) {
enter[node] = timer++;
euler.push_back({d, node});
for(auto nxt : graph[node]) {
if(nxt == par) continue;
dfs(nxt, node, d + 1, graph);
euler.push_back({d, node});
timer++;
}
}
int lca(int u, int v) {
int L = min(enter[u], enter[v]);
int R = max(enter[u], enter[v]);
int j = log_table[R - L + 1];
pii a = st[j][L], b = st[j][R - (1 << j) + 1];
return (a.first < b.first ? a : b).second;
}
};
// ------------------- GRAPH Class -----------------------
template<typename T = int>
class GRAPH {
public:
int n, m;
vvi dp;
vi depth, parent, subtree;
vi tin, tout, ord;
int timer = 0;
LCA_O1<T> lca_01;
GRAPH() {}
GRAPH(const vt<vt<T>>& graph, int root = 0) : lca_01(graph, root) {
n = graph.size();
m = floor(log2(n)) + 1;
dp.resize(n, vi(m, root)); // initialize dp with root (0 in our case)
depth.resize(n, 0);
parent.resize(n, -1);
subtree.resize(n, 1);
tin.resize(n);
tout.resize(n);
ord.resize(n);
dfs(graph, root, -1);
init();
}
void dfs(const vt<vt<T>>& graph, int node, int par) {
tin[node] = timer++;
ord[tin[node]] = node;
for(auto nxt : graph[node]) {
if(nxt == par) continue;
depth[nxt] = depth[node] + 1;
dp[nxt][0] = node;
parent[nxt] = node;
dfs(graph, nxt, node);
subtree[node] += subtree[nxt];
}
tout[node] = timer - 1;
}
bool isAncestor(int u, int v) {
return tin[u] <= tin[v] && tin[v] <= tout[u];
}
void init() {
for(int j = 1; j < m; j++) {
for(int i = 0; i < n; i++) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
}
int lca(int a, int b) {
return lca_01.lca(a, b);
}
int dist(int u, int v) {
int a = lca(u, v);
return depth[u] + depth[v] - 2 * depth[a];
}
};
// ------------------- Main solve() -----------------------
const int MK = 20;
void solve() {
int n, m, q;
cin >> n >> m >> q;
vpii edges(n - 1);
vvi graph(n);
for(int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--; // convert input to 0-indexing
edges[i] = {u, v};
graph[u].push_back(v);
graph[v].push_back(u);
}
// Build GRAPH with root 0.
GRAPH<int> g(graph, 0);
// Reorient edges so that for each edge, the first is parent and second is child.
for(int i = 0; i < n - 1; i++) {
auto &e = edges[i];
int u = e.first, v = e.second;
if(g.parent[v] != u) swap(u, v);
e = {u, v}; // now u is parent, v is child.
}
// Build a BIT (FW) for indices 0..n-1 (Euler tour indices)
FW<int> BITree(n, 0, [](const int &a, const int &b) { return a + b; });
// Initialize BIT: for each node i, update at position tin[i] with +1.
for (int i = 0; i < n; i++) {
BITree.update_at(g.tin[i], 1);
}
// Use full dp table size for binary lifting.
int liftSize = g.dp[0].size();
auto find_par = [&](int u) -> int {
int x = BITree.get(g.tin[u]);
for (int j = liftSize - 1; j >= 0; j--) {
int p = g.dp[u][j];
// safety check: p should be in range [0, n)
if(p < 0 || p >= n) continue;
if(BITree.get(g.tin[p]) == x)
u = p;
}
return u;
};
// used[] for edge toggling; initialize ans[] to 1 for every node.
vi used(n - 1, 0), ans(n, 1), del(n, 0);
while(m--) {
int k;
cin >> k;
k--; // convert edge id to 0-index.
auto &e = edges[k];
int u = e.first, v = e.second;
if(!used[k]) { // Remove edge: "cut" the subtree v from u.
ans[find_par(u)] += ans[v] - del[v];
BITree.update_range(g.tin[v], g.tout[v], -1);
} else { // Add edge: "merge" subtree v back with u.
ans[v] = del[v] = ans[find_par(u)];
BITree.update_range(g.tin[v], g.tout[v], 1);
}
used[k] ^= 1;
}
while(q--) {
int u;
cin >> u;
u--; // convert query to 0-index.
cout << ans[find_par(u)] << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |