//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef __APPLE__
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct stmnmx {
static const int Nmax = 5e5 + 42;
int Nst;
pair<int, int> st[Nmax * 4];
pair<int, int> id = {-1e9, -1e9};
#define mnmx max
pair<int, int> get_(int l, int r, int v, int tl, int tr) {
if (l > r) return id;
if (l == tl && r == tr) return st[v];
int tm = ((tl + tr) >> 1);
return mnmx(get_(l, min(r, tm), (v << 1), tl, tm), get_(max(l, tm + 1), r, (v << 1) + 1, tm + 1, tr));
}
pair<int, int> get(int l, int r) {
return get_(l, r, 1, 0, Nst - 1);
}
void upd_(int pos, pair<int, int> new_v, int v, int tl, int tr) {
if (tl == tr) st[v] = new_v;
else {
int tm = ((tl + tr) >> 1);
if (pos <= tm) upd_(pos, new_v, (v << 1), tl, tm);
else upd_(pos, new_v, (v << 1) + 1, tm + 1, tr);
st[v] = mnmx(st[(v << 1)], st[(v << 1) + 1]);
}
}
void upd(int pos, pair<int, int> new_v) {
return upd_(pos, new_v, 1, 0, Nst - 1);
}
};
stmnmx st;
struct HLD {
static const int maxN = 1e5 + 42;
vector<int> g[maxN];
int head[maxN] = {}, parent[maxN] = {}, depth[maxN] = {}, subt[maxN] = {};
int pos[maxN] = {};
int curpos = 0;
bool VALS_IN_EDGES = 0;
void init(int root) {
parent[root] = depth[root] = curpos = 0;
predfs(root);
head[root] = root;
dfsHLD(root);
}
void add_edge(int a, int b) {
g[a].pb(b);
g[b].pb(a);
}
void predfs(int v) {
subt[v] = 1;
for (auto &to: g[v]) {
parent[to] = v;
depth[to] = depth[v] + 1;
g[to].erase(find(all(g[to]), v));
predfs(to);
subt[v] += subt[to];
if (subt[to] > subt[g[v][0]]) swap(g[v][0], to);
}
}
void dfsHLD(int v) {
pos[v] = curpos++;
for (auto &to: g[v]) {
head[to] = (to == g[v][0] ? head[v] : to);
dfsHLD(to);
}
}
int lca(int a, int b) {
for (; head[a] != head[b]; b = parent[head[b]]) {
if (depth[head[a]] > depth[head[b]]) swap(a, b);
}
if (depth[a] > depth[b]) swap(a, b);
return a;
}
pair<int, int> query_path(int a, int b) {
pair<int, int> res = st.id;
for (; head[a] != head[b]; b = parent[head[b]]) {
if (depth[head[a]] > depth[head[b]]) swap(a, b);
res = max(res, st.get(pos[head[b]], pos[b]));
}
if (depth[a] > depth[b]) swap(a, b);
res = max(res, st.get(pos[a] + VALS_IN_EDGES, pos[b]));
return res;
}
};
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int> > edges(n - 1);
HLD hld;
for(int i = 0; i < n - 1; i++) {
cin >> edges[i].fi >> edges[i].se;
edges[i].fi--; edges[i].se--;
hld.add_edge(edges[i].fi, edges[i].se);
}
hld.init(0);
st.Nst = n;
for(int i = 0; i < n; i++) {
st.upd(hld.pos[i], {hld.depth[i], i});
}
vector<int> active(n - 1);
vector<int> ans(n, 1), last_sync(n);
while(m--) {
int edg; cin >> edg; edg--;
int x = edges[edg].fi, y = edges[edg].se;
if(hld.depth[x] > hld.depth[y]) swap(x, y);
int rootx = hld.query_path(0, x).se;
if(!active[edg]) {
int nval = ans[rootx] + ans[y] - last_sync[y];
ans[rootx] = ans[y] = last_sync[y] = nval;
st.upd(hld.pos[y], st.id);
} else {
ans[y] = last_sync[y] = ans[rootx];
st.upd(hld.pos[y], {hld.depth[y], y});
}
active[edg] ^= 1;
}
while(q--) {
int v; cin >> v; cout << ans[--v] << '\n';
}
}
signed main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
}
/*
KIVI
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
20180 KB |
Output is correct |
| 2 |
Correct |
8 ms |
20280 KB |
Output is correct |
| 3 |
Correct |
9 ms |
20272 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
20196 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
31388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
20284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
36164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
20284 KB |
Output is correct |
| 2 |
Correct |
8 ms |
20180 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
20180 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
