#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
mt19937 rnd(228);
struct Node {
int x, y, cnt;
Node *l, *r;
Node (int x_) {
x = x_; y = rnd();
l = r = NULL;
cnt = 1;
}
};
int cnt(Node *t) {
if (!t) return 0;
else return t->cnt;
}
void relax(Node *t) {
t->cnt = cnt(t->l) + cnt(t->r) + 1;
}
Node *merge(Node *l, Node *r) {
if (!l) return r;
if (!r) return l;
if (l->y < r->y) {
l->r = merge(l->r, r);
relax(l);
return l;
}
else {
r->l = merge(l, r->l);
relax(r);
return r;
}
}
pair <Node*, Node*> split(Node *t, int x) {
if (!t) return {NULL, NULL};
if (t->x < x) {
auto tmp = split(t->r, x);
t->r = tmp.first;
relax(t);
return {t, tmp.second};
}
else {
auto tmp = split(t->l, x);
t->l = tmp.second;
relax(t);
return {tmp.first, t};
}
}
void insert(Node *&t, int x) {
auto tmp = split(t, x);
t = merge(merge(tmp.first, new Node(x)), tmp.second);
}
void erase(Node *&t, int x) {
auto tmp = split(t, x);
auto tmp1 = split(tmp.second, x + 1);
t = merge(tmp.first, tmp1.second);
}
Node *get(Node *&t, int l, int r) {
auto tmp = split(t, l);
auto tmp1 = split(tmp.second, r + 1);
t = merge(tmp.first, tmp1.second);
return tmp1.first;
}
const int N = 1e5 + 7;
Node *dd[N][2];
vector <int> g[N];
int vert[N];
int l[N], r[N], ptr = 0;
void dfs(int u, int p) {
l[u] = ++ptr;
vert[ptr] = u;
for (int v : g[u]) {
if (v != p) {
dfs(v, u);
}
}
r[u] = ptr;
}
int mx[N << 2];
void upd(int v, int tl, int tr, int p, int x) {
if (tl == tr) {
mx[v] = x;
return;
}
int tm = (tl + tr) >> 1;
if (p <= tm) upd(v * 2 + 1, tl, tm, p, x);
else upd(v * 2 + 2, tm + 1, tr, p, x);
mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
int parent(int v, int tl, int tr, int l, int r, int x) {
if (tr < l || r < tl || mx[v] < x) return -1;
if (tl == tr) return vert[tl];
int tm = (tl + tr) >> 1;
int t = parent(v * 2 + 2, tm + 1, tr, l, r, x);
if (t != -1) return t;
else return parent(v * 2 + 1, tl, tm, l, r, x);
}
int ans = 0;
void initialize(int n, vector <int> a, vector <int> b) {
for (int i = 0; i < n - 1; ++i) {
g[a[i]].app(b[i]);
g[b[i]].app(a[i]);
}
++n;
g[0].app(1);
dfs(0, 0);
for (int i = 0; i < (N << 2); ++i) {
mx[i] = -1;
}
upd(0, 0, N, l[0], r[0]);
}
//0 - cat, 1 - dog
int type[N];
void add(int u) {
int p = parent(0, 0, N, 0, l[u] - 1, r[u]);
ans += type[u] ^ type[p];
for (int i = 0; i < 2; ++i) {
dd[u][i] = get(dd[p][i], l[u], r[u]);
if (type[u] ^ type[p]) {
if (i == type[u]) {
ans -= cnt(dd[u][i]);
}
else {
ans += cnt(dd[u][i]);
}
}
}
insert(dd[p][type[u]], l[u]);
upd(0, 0, N, l[u], r[u]);
}
void del(int u) {
int p = parent(0, 0, N, 0, l[u] - 1, r[u]);
ans -= type[u] ^ type[p];
erase(dd[p][type[u]], l[u]);
for (int i = 0; i < 2; ++i) {
if (type[u] ^ type[p]) {
if (i == type[u]) {
ans += cnt(dd[u][i]);
}
else {
ans -= cnt(dd[u][i]);
}
}
auto tmp = split(dd[p][i], l[u]);
auto tmp1 = split(dd[p][i], r[u] + 1);
dd[p][i] = merge(merge(tmp.first, dd[u][i]), tmp1.second);
dd[u][i] = NULL;
}
upd(0, 0, N, l[u], -1);
}
int f() {
#ifdef HOME0
cout << ans << ' ' << cnt(dd[0][0]) << ' ' << cnt(dd[0][1]) << '\n';
#endif
return ans - cnt(dd[0][1]) + min(cnt(dd[0][0]), cnt(dd[0][1]));
}
int cat(int u) {
type[u] = 0;
add(u);
return f();
}
int dog(int u) {
type[u] = 1;
add(u);
return f();
}
int neighbor(int u) {
del(u);
return f();
}
#ifdef HOME
signed main() {
freopen("input.txt", "r", stdin);
int n;
cin >> n;
vector <int> a, b;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
a.app(u); b.app(v);
}
initialize(n, a, b);
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int t, u;
cin >> t >> u;
if (t == 1) cout << cat(u) << '\n';
else if (t == 2) cout << dog(u) << '\n';
else cout << neighbor(u) << '\n';
}
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
4216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
4216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
4216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
