//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 200005
using namespace std;
const ll inf = 1e9;
bool ghuy4g;
vector<ll> adj[N];
pii canh[N];
ll n, m, q, par[N], st[4 * N];
ll sz[N], pos[N], tour[N], chain_head[N], chain_id[N], high[N];
ll cur_pos = 1, cur_chain = 1;
void update(ll id, ll l, ll r, ll i, ll v) {
if (i > r || i < l) return;
if (l == r) {
st[id] = v;
return;
}
ll mid = (l + r) / 2;
update(id * 2, l, mid, i, v);
update(id * 2 + 1, mid + 1, r, i, v);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
ll get(ll id, ll l, ll r, ll L, ll R) {
if (l > R || r < L) return -inf;
if (L <= l && r <= R) {
return st[id];
}
ll mid = (l + r) / 2;
return max(get(id * 2, l, mid, L, R), get(id * 2 + 1, mid + 1, r, L, R));
}
void dfs(ll u, ll parent) {
sz[u] = 1;
for (auto v : adj[u]) {
if (v == parent) continue;
par[v] = u;
high[v] = high[u] + 1;
dfs(v, u);
sz[u] += sz[v];
}
}
ll lca(ll u, ll v) {
while (chain_id[u] != chain_id[v]) {
//cout << u << " " << v << " " << chain_id[u] << " " << chain_id[v] << endl;
//cout << chain_head[chain_id[u]] << " " << chain_head[chain_id[v]] << endl;
if (high[chain_head[chain_id[u]]] > high[chain_head[chain_id[v]]]) {
u = par[chain_head[chain_id[u]]];
}
else {
v = par[chain_head[chain_id[v]]];
}
}
if (high[u] < high[v]) return u;
return v;
}
ll qr(ll u, ll v) {
//return 1;
ll res = -inf;
ll x = lca(u, v);
//return 1;
while (chain_id[u] != chain_id[x]) {
ll r = chain_head[chain_id[u]];
res = max(res, get(1, 1, n, pos[r], pos[u]));
u = par[r];
}
while (chain_id[v] != chain_id[x]) {
ll r = chain_head[chain_id[v]];
res = max(res, get(1, 1, n, pos[r], pos[v]));
v = par[r];
}
if (high[u] < high[v]) {
res = max(res, get(1, 1, n, pos[u], pos[v]));
}
else {
res = max(res, get(1, 1, n, pos[v], pos[u]));
}
return res;
}
void hld(ll u, ll parent) {
if (chain_head[cur_chain] == 0) {
//cout << "head " << chain_id[u] << " " << u << endl;
chain_head[cur_chain] = u;
}
pos[u] = cur_pos;
tour[cur_pos] = u;
chain_id[u] = cur_chain;
//cout << u << " chain " << cur_chain << endl;
cur_pos ++ ;
ll nxt = 0;
for (auto v : adj[u]) {
if (v == parent) continue;
if (sz[v] > sz[nxt]) {
nxt = v;
}
}
if (nxt) {
hld(nxt, u);
}
for (auto v : adj[u]) {
if (v == parent || v == nxt) continue;
cur_chain ++ ;
hld(v, u);
}
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = -inf;
return;
}
ll mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
void pre() {
dfs(1, 1);
cur_chain = cur_pos = 1;
hld(1, 1);
build(1, 1, n);
for (int i = 1; i <= n - 1; i ++) {
if (par[canh[i].fi] == canh[i].se) {
swap(canh[i].fi, canh[i].se);
}
}
}
ll find(ll u) {
//cout << "find " << u << endl;
ll x = qr(1, u);
/*if (x != qr(u, 1)) {
cout << "ngu";
exit(3);
}*/
if (x == -inf) return 1;
return tour[x];
}
ll a[N], c[N];
bool is[N];
void solve() {
for (int i = 1; i <= m; i ++) {
ll id;
cin >> id;
ll u = canh[id].fi, v = canh[id].se;
if (is[id] == 0) {
// noi u v
ll ru = find(u); // rv == v
ll moi = a[ru] + a[v] - c[v];
//cout << u << " " << v << " ru " << ru << " " << moi << endl;
update(1, 1, n, pos[v], -inf);
a[ru] = moi;
}
else {
ll ru = find(u);
a[v] = c[v] = a[ru];
//cout << "go ra " << ru << " " << v << " a[v] " << a[v] << endl;
update(1, 1, n, pos[v], pos[v]);
}
is[id] = 1 - is[id];
}
for (int i = 1; i <= q; i ++) {
ll u; cin >> u;
cout << a[find(u)] << endl;
}
}
bool klinh;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n - 1; i ++) {
a[i] = 1; a[i + 1] = 1;
ll u, v;
cin >> u >> v;
canh[i] = {u, v};
adj[u].push_back(v);
adj[v].push_back(u);
}
pre();
solve();
cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
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... |