#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast,unroll-loops")
//pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define pb push_back
#define cl clear
#define minr(a, b) a = min(a, b);
#define maxr(a, b) a = max(a, b);
#define shit cout << "shit\n" << flush;
#define tl while(1&1) continue;
#define FOR(i, st, nd) for(int i = st; i <= n; i++)
#define rand(l, r) uniform_int_distribution<int64_t>(l,r)(rng)
random_device device; default_random_engine rng(device());
const int Mod = 1e9 + 7; //998244353;
const int LG = 64;
const int SQ = 500;
const int Inf = 2e9 + 10;
const int maxN = 1e5 + 10;
int n, m, q;
int tim = 1;
int h[maxN];
int st[maxN];
int ft[maxN];
int cur[maxN];
int lst[maxN];
int stNode[maxN];
bool mark[maxN];
bool active[maxN];
vector <int> neighb[maxN];
vector <pii> edges;
struct RootSegTree {
struct Node {
int MxR;
Node() {
MxR = 0;
}
} t[maxN<<2];
void initialize(int id, int L, int R) {
if(L+1 == R) {
t[id].MxR = ft[stNode[L]];
return;
}
int mid = (L+R)>>1;
initialize(2*id+0, L, mid);
initialize(2*id+1, mid, R);
t[id].MxR = max(t[2*id+0].MxR, t[2*id+1].MxR);
}
void update(int id, int L, int R, int idx, int val) {
if(L+1 == R) {
t[id].MxR = val;
return ;
}
int mid = (L+R)>>1;
if(idx < mid)
update(2*id+0, L, mid, idx, val);
else
update(2*id+1, mid, R, idx, val);
t[id].MxR = max(t[2*id+0].MxR, t[2*id+1].MxR);
}
int search(int id, int L, int R, int val) {
if(L+1 == R)
return L;
int mid = (L+R)>>1;
if(t[2*id+1].MxR >= val)
return search(2*id+1, mid, R, val);
return search(2*id+0, L, mid, val);
}
int GetRoot(int id, int L, int R, int l, int r, int val) {
if(t[id].MxR < val)
return -1;
if(L == l and R == r)
return search(id, L, R, val);
int mid = (L+R)>>1;
if(r <= mid)
return GetRoot(2*id+0, L, mid, l, min(mid, r), val);
int tmp = GetRoot(2*id+1, mid, R, max(l, mid), r, val);
if(tmp >= 1)
return tmp;
return GetRoot(2*id+0, L, mid, l, min(mid, r), val);
}
} rst;
void dfs(int u) {
st[u] = tim;
stNode[tim] = u;
tim++;
mark[u] = true;
for(auto v : neighb[u]) {
if(!mark[v]) {
dfs(v);
}
}
ft[u] = tim-1;
}
int main() {
IOS;
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n-1; i++) {
int u, v;
cin >> u >> v;
neighb[u].pb(v);
neighb[v].pb(u);
edges.pb({u, v});
}
dfs(1);
rst.initialize(1, 1, n+1);
for(int i = 1; i <= n; i++)
cur[i] = 1;
while(m--) {
int idx;
cin >> idx;
int u = edges[idx-1].F;
int v = edges[idx-1].S;
if(st[u] > st[v])
swap(u, v);
if(active[idx]) {
active[idx] = false;
int root = rst.GetRoot(1, 1, n+1, 1, st[v]+1, st[v]);
rst.update(1, 1, n+1, st[v], ft[v]);
cur[v] = cur[stNode[root]];
lst[v] = cur[v];
}
else {
active[idx] = true;
int root = rst.GetRoot(1, 1, n+1, 1, st[u]+1, st[u]);
rst.update(1, 1, n+1, st[v], 0);
cur[stNode[root]] += (cur[v]-lst[v]);
}
}
while(q--) {
int u;
cin >> u;
int root = rst.GetRoot(1, 1, n+1, 1, st[u]+1, st[u]);
cout << cur[stNode[root]] << "\n";
}
}
# | 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... |