#pragma GCC optimize("conserve-stack")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define iter(id, v) for(auto id : v)
#define fs first
#define se second
#define MP make_pair
#define pb push_back
#define bit(msk, i) ((msk >> i) & 1)
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e5 + 7;
const int M = 1e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;
int n, Q, K;
pii ed[N];
vector<int> ke[M];
int pid[N];
int pa[M], nC[M], high[M], par[M][25];
int Head[M], ein[M];
bool stt[M];
struct Node2 {
Node2 *lc, *rc;
int val;
Node2 () {
lc = rc = NULL;
val = 0;
}
Node2 (int _val) {
lc = rc = NULL;
val = _val;
}
Node2 (Node2 *lcc, Node2 *rcc) {
lc = lcc;
rc = rcc;
val = max(lcc->val, rcc->val);
}
};
struct Node {
Node *lc, *rc;
int val;
Node () {
lc = rc = NULL;
val = 0;
}
Node (int _val) {
lc = rc = NULL;
val = _val;
}
Node (Node *lcc, Node *rcc) {
lc = lcc;
rc = rcc;
val = lcc->val & rcc->val;
}
};
Node *croot[N];
Node2 *croot2[N];
struct Persistent_Segment_Tree {
int m;
Node *build (int l, int r) {
if (l == r) return new Node();
int mid = l + r >> 1;
return new Node(build (l, mid), build (mid + 1, r));
}
void init (int n) {
m = n;
croot[0] = build(1, m);
}
Node *update (Node *curr, int l, int r, int pos) {
if (l == r) {
Node *cur = new Node(0);
cur->val = curr->val ^ 1;
return cur;
}
int mid = l + r >> 1;
if (mid < pos)
return new Node(curr->lc, update (curr->rc, mid + 1, r, pos));
else
return new Node(update (curr->lc, l, mid, pos), curr->rc);
}
int get (Node *curr, int l, int r, int u, int v) {
if (l > v || r < u) return 1;
if (l >= u && r <= v) return curr->val;
int mid = l + r >> 1;
return get (curr->lc, l, mid, u, v) & get (curr->rc, mid + 1, r, u, v);
}
void update (int pos) {
static int n_root = 0;
++n_root;
croot[n_root] = update (croot[n_root - 1], 1, m, pos);
}
int get (Node* rt, int u, int v ) {
return get (rt, 1, m, u, v);
}
}ST;
struct Persistent_Segment_Tree2 {
int m;
Node2 *build (int l, int r) {
if (l == r) return new Node2(1);
int mid = l + r >> 1;
return new Node2(build (l, mid), build (mid + 1, r));
}
void init (int n) {
m = n;
croot2[0] = build(1, m);
}
Node2 *update (Node2 *curr, int l, int r, int pos, int val, bool typ) {
if (l == r) {
Node2 *cur = new Node2(0);
if (typ == 1) {
cur->val = val;
}
else {
cur->val = curr->val + val;
}
return cur;
}
int mid = l + r >> 1;
if (mid < pos)
return new Node2(curr->lc, update (curr->rc, mid + 1, r, pos, val, typ));
else
return new Node2(update (curr->lc, l, mid, pos, val, typ), curr->rc);
}
int get (Node2 *curr, int l, int r, int pos) {
if (l > pos || r < pos) return 0;
if (l == r) return curr->val;
int mid = l + r >> 1;
return max(get (curr->lc, l, mid, pos), get (curr->rc, mid + 1, r, pos));
}
void update (int pos, int val, bool typ) {
static int n_root = 0;
++n_root;
croot2[n_root] = update (croot2[n_root - 1], 1, m, pos, val, typ);
}
int get (Node2 *rt, int pos) {
return get (rt, 1, m, pos);
}
}ST2;
void pdfs (int u, int p) {
high[u] = high[p] + 1;
pa[u] = p;
par[u][0] = p;
rep (i, 1, 20) par[u][i] = par[par[u][i - 1]][i - 1];
nC[u] = 1;
iter (&v, ke[u]) {
if (v != p) {
pdfs(v, u);
nC[u] += nC[v];
}
}
}
void hld (int u, int p) {
static int time_dfs = 0;
Head[u] = p;
ein[u] = ++time_dfs;
int mxV = -1;
iter (&v, ke[u]) if (v != pa[u] && (mxV == -1 || nC[v] > nC[mxV])) mxV = v;
if (mxV != -1) hld(mxV, p);
iter (&v, ke[u]) {
if (v == pa[u] || v == mxV) continue;
hld(v, v);
}
}
int label (int state, int u) {
while (u != 0) {
bool cnc = ST.get(croot[state], ein[Head[u]], ein[u]);
if (cnc == 0) {
if (ST.get(croot[state], ein[u], ein[u]) == 0) return u;
reb (i, 20, 0) {
int cur = par[u][i];
if (high[cur] >= high[Head[u]] && ST.get(croot[state], ein[cur], ein[u])) {
u = cur;
}
}
return pa[u];
}
u = pa[Head[u]];
}
}
int getVal (int state, int u) {
return ST2.get(croot2[state], ein[label(state, u)]);
}
void Connect (int state, int p) {
int u = ed[p].fs, v = ed[p].se;
int prvid = pid[p];
if (high[u] > high[v]) swap(u, v);
int delta = getVal(state - 1, v);
if (pid[p] != -1) {
delta -= getVal(pid[p], v);
}
// cout << u <<" "<<v<<" "<<getVal(state - 1,u)<<" "<<getVal(state - 1, v)<< " " <<delta<<"\n";
ST2.update (ein[label(state - 1, u)], delta, 0);
ST.update (ein[v]);
}
void Detach (int state, int p) {
int u = ed[p].fs, v = ed[p].se;
if (high[u] > high[v]) swap(u, v);
int delta = getVal(state - 1, u);
ST2.update (ein[v], delta, 1);
ST.update (ein[v]);
pid[p] = state;
}
void solution () {
cout << sizeof (par) / (1 << 20);
return;
cin >> n >> Q >> K;
rep (i, 1, n - 1) {
int u, v;
cin >> u >> v;
ed[i] = MP(u, v);
ke[u].pb(v);
ke[v].pb(u);
}
pdfs(1, 0);
hld(1, 1);
ST.init(n);
ST2.init(n);
rep (i, 1, n) pid[i] = -1;
rep (i, 1, Q) {
int p;
cin >> p;
stt[p] ^= 1;
if (stt[p] == 1) {
Connect(i, p);
}
else {
Detach(i, p);
}
}
rep (i, 1, K) {
int X;
cin >> X;
cout << getVal(Q, X) <<"\n";
}
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
10 20 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
9
4
6
3
5
3
6
9
3
7
2
4
8
2
5
1
6
5
1
6
6
*/
Compilation message
synchronization.cpp: In member function 'Node* Persistent_Segment_Tree::build(int, int)':
synchronization.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid = l + r >> 1;
| ~~^~~
synchronization.cpp: In member function 'Node* Persistent_Segment_Tree::update(Node*, int, int, int)':
synchronization.cpp:101:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int mid = l + r >> 1;
| ~~^~~
synchronization.cpp: In member function 'int Persistent_Segment_Tree::get(Node*, int, int, int, int)':
synchronization.cpp:111:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | int mid = l + r >> 1;
| ~~^~~
synchronization.cpp: In member function 'Node2* Persistent_Segment_Tree2::build(int, int)':
synchronization.cpp:131:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
131 | int mid = l + r >> 1;
| ~~^~~
synchronization.cpp: In member function 'Node2* Persistent_Segment_Tree2::update(Node2*, int, int, int, int, bool)':
synchronization.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
151 | int mid = l + r >> 1;
| ~~^~~
synchronization.cpp: In member function 'int Persistent_Segment_Tree2::get(Node2*, int, int, int)':
synchronization.cpp:161:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
161 | int mid = l + r >> 1;
| ~~^~~
synchronization.cpp: In function 'void Connect(int, int)':
synchronization.cpp:226:9: warning: unused variable 'prvid' [-Wunused-variable]
226 | int prvid = pid[p];
| ^~~~~
synchronization.cpp: In function 'int label(int, int)':
synchronization.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
218 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
