#ifdef LOCAL
#include "/home/bgopc/template/pch.hpp"
#endif
#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;
int n, m, q, in[maxn], out[maxn], T = 1, sz[maxn], ans[maxn], lst[maxn], up[maxn][LG], fen[maxn], active[maxn];
vector<int> g[maxn];
pii E[maxn];
void dfs(int v, int p = 0) {
up[v][0] = p;
for (int i = 1 ; i < LG ; i ++) up[v][i] = up[up[v][i - 1]][i - 1];
in[v] = T ++;
for (int u : g[v]) {
if (u != p) dfs(u, v);
}
out[v] = T;
}
inline void add(int p, int x) {
for (; p <= n + 1 ; p += p & -p) fen[p] += x;
}
inline int get(int p) {
int res = 0;
for (; p ; p -= p & -p) res += fen[p];
return res;
}
inline int root(int v) {
int u = v;
for (int i = LG - 1 ; i >= 0 ; i --) {
if (up[u][i] && get(in[up[u][i]]) == get(in[v])) u = up[u][i];
}
return u;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1 , u ,v ; i <= n - 1 ; i ++) {
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
E[i] = {u, v};
}
dfs(1);
for (int i = 1 ; i <= n ; i ++) ans[i] = 1;
for (int i = 1 ; i <= n - 1 ; i ++) {
auto &&[u, v] = E[i];
if (v == up[u][0]) swap(u, v);
add(in[v], 1);
add(out[v], -1);
}
for (int e ; m -- ; ) {
cin >> e;
auto [u, v] = E[e];
if (active[e]) {
ans[v] = lst[v] = ans[root(u)];
add(in[v], 1);
add(out[v], -1);
} else {
ans[root(u)] += ans[v] - lst[v];
add(in[v], -1);
add(out[v], +1);
}
active[e] ^= 1;
}
for (int v ; q -- ; ) {
cin >> v;
cout << ans[root(v)] << nl;
}
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... |