#include <bits/stdc++.h>
#define task "BriantheCrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}
const int maxN = 2e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
const int LOG = 20;
// khong tu code thi khong kha len duoc dau
// biet sol roi thi tu lam not di
struct Fenwick {
vector <int> bit;
int n;
inline void init () {
bit.resize (n + 2, 0);
}
inline void upd (int id, int val) {
for (; id < n; id += id & (-id)) {
bit[id] += val;
}
}
inline int get (int id) {
int res = 0;
for (; id; id -= id & (-id)) {
res += bit[id];
}
return res;
}
};
int n, m, q;
int res[maxN], lst[maxN], up[maxN][LOG], h[maxN];
int tIn[maxN], tOut[maxN];
int timer = 0;
vector <pii> ed;
vector <int> adj[maxN];
bool merged[maxN];
Fenwick T;
void dfs (int u, int p) {
up[u][0] = p;
tIn[u] = ++timer;
for (int j = 1; j < LOG; j ++) {
up[u][j] = up[up[u][j - 1]][j - 1];
}
for (auto v : adj[u]) {
if (v == p) {
continue;
}
h[v] = h[u] + 1;
dfs (v, u);
}
tOut[u] = timer;
}
inline int jump (int u) {
for (int j = LOG - 1; j >= 0; j --) {
if (T.get (tIn[up[u][j]]) == T.get (tIn[u])) {
u = up[u][j];
}
}
return u;
}
inline void print () {
cout << "print\n";
for (int i = 1; i <= n; i ++) {
cout << T.get (tIn[i]) << ' ';
}
cout << '\n';
}
void solve () {
cin >> n >> m >> q;
for (int i = 1; i <= n - 1; i ++) {
int u, v;
cin >> u >> v;
adj[u].push_back (v);
adj[v].push_back (u);
ed.push_back ({u, v});
}
dfs (1, 1);
T.n = timer + 2;
T.init ();
for (int i = 1; i <= n; i ++) {
res[i] = 1;
T.upd (tIn[i], 1);
T.upd (tOut[i] + 1, -1);
}
//print ();
for (int i = 1; i <= m; i ++) {
int x;
cin >> x;
auto [u, v] = ed[x - 1];
if (h[u] > h[v]) {
swap (u, v);
}
if (merged[x] == 0) {
//cout << u << ' ' << v << ' ' << jump (u) << '\n';
res[jump (u)] += res[v] - lst[v];
T.upd (tIn[v], -1);
T.upd (tOut[v] + 1, 1);
//cout << tIn[i] << ' ' << tOut[i] << '\n';
merged[x] = 1;
}
else {
res[v] = lst[v] = res[jump (u)];
T.upd (tIn[v], 1);
T.upd (tOut[v] + 1, -1);
//cout << tIn[i] << ' ' << tOut[i] << '\n';
merged[x] = 0;
}
//print ();
}
while (q --) {
int x;
cin >> x;
cout << res[jump (x)] << '\n';
}
return;
}
signed main () {
cin.tie (nullptr) -> sync_with_stdio (false);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int t = 1;
//cin >> t;
while (t --) {
solve ();
}
return 0;
}
// thfv
Compilation message (stderr)
synchronization.cpp: In function 'int main()':
synchronization.cpp:148:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen (task".inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:149:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | freopen (task".out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |