#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int N, par[maxn], sz[maxn];
int pos[maxn], _Time, flat[maxn], anc[maxn];
int ans;
bool hut[maxn];
vector<int> A, B, adj[maxn];
struct segment_tree {
int loc;
array<int, 2> stat, lazy;
} st[4*maxn];
void dfs_sz(int s, int p) {
sz[s] = 1;
par[s] = p;
if(int(adj[s].size()) >= 2 && adj[s][0] == p)
swap(adj[s][0], adj[s][1]);
for(int& u : adj[s]) {
if(u != p) {
dfs_sz(u, s);
sz[s] += sz[u];
if(sz[u] > sz[adj[s][0]])
swap(u, adj[s][0]);
}
}
}
void build_hld(int s) {
pos[s] = _Time;
flat[_Time] = s;
++_Time;
for(int& u : adj[s]) {
if(u != par[s]) {
if(u == adj[s][0])
anc[u] = anc[s];
else
anc[u] = u;
build_hld(u);
}
}
}
int LCA(int u, int v) {
if(pos[u] < pos[v])
swap(u, v);
if(anc[u] == anc[v])
return v;
return LCA(par[anc[u]], v);
}
void build_st(int v, int tl, int tr) {
if(tl == tr) {
st[v].loc = -1;
st[v].stat[0] = st[v].stat[1] = 0;
st[v].lazy[0] = st[v].lazy[1] = 0;
return;
}
int tm = (tl + tr) / 2;
build_st(2 * v + 1, tl, tm);
build_st(2 * v + 2, tm + 1, tr);
st[v].loc = -1;
st[v].stat[0] = st[v].stat[1] = 0;
st[v].lazy[0] = st[v].lazy[1] = 0;
}
void initialize(int _N, vector<int> _A, vector<int> _B) {
swap(N, _N);
swap(A, _A);
swap(B, _B);
for (int i = 0; i <= N-2; ++i) {
--A[i];
--B[i];
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs_sz(0, -1);
build_hld(0);
build_st(0, 0, N-1);
}
void flip(int v, int tl, int tr, int ind) {
if(tl == tr) {
if(st[v].loc == -1)
st[v].loc = flat[tl];
else
st[v].loc = -1;
return;
}
int tm = (tl + tr) / 2;
if(ind <= tm)
flip(2 * v + 1, tl, tm, ind);
else
flip(2 * v + 2, tm + 1, tr, ind);
st[v].loc = st[2 * v + 2].loc;
if(st[v].loc == -1)
st[v].loc = st[2 * v + 1].loc;
}
void flip(int s) {
flip(0, 0, N - 1, pos[s]);
}
int get_loc(int v, int tl, int tr, int l, int r) {
if(tl == l && tr == r)
return st[v].loc;
int tm = (tl + tr) / 2;
if(r <= tm)
return get_loc(2 * v + 1, tl, tm, l, r);
if(l > tm)
return get_loc(2 * v + 2, tm + 1, tr, l, r);
int T = get_loc(2 * v + 2, tm + 1, tr, tm + 1, r);
if(T != -1)
return T;
return get_loc(2 * v + 1, tl, tm, l, tm);
}
int get_loc(int s) {
int res = get_loc(0, 0, N - 1, pos[anc[s]], pos[s]);
if(res != -1)
return res;
if(!anc[s])
return -1;
return get_loc(par[anc[s]]);
}
void push_down(int v) {
st[2 * v + 1].stat[0] += st[v].lazy[0];
st[2 * v + 1].stat[1] += st[v].lazy[1];
st[2 * v + 2].stat[0] += st[v].lazy[0];
st[2 * v + 2].stat[1] += st[v].lazy[1];
st[2 * v + 1].lazy[0] += st[v].lazy[0];
st[2 * v + 1].lazy[1] += st[v].lazy[1];
st[2 * v + 2].lazy[0] += st[v].lazy[0];
st[2 * v + 2].lazy[1] += st[v].lazy[1];
st[v].lazy[0] = st[v].lazy[1] = 0;
}
array<int, 2> val(int v, int tl, int tr, int ind) {
if(tl == tr)
return st[v].stat;
push_down(v);
int tm = (tl + tr) / 2;
if(ind <= tm)
return val(2 * v + 1, tl, tm, ind);
return val(2 * v + 2, tm + 1, tr, ind);
}
array<int, 2> val(int s) {
return val(0, 0, N - 1, pos[s]);
}
void add(int v, int tl, int tr, int l, int r, array<int, 2> a) {
if(tl == l && tr == r) {
st[v].stat[0] += a[0];
st[v].stat[1] += a[1];
st[v].lazy[0] += a[0];
st[v].lazy[1] += a[1];
return;
}
push_down(v);
int tm = (tl + tr) / 2;
if(r <= tm)
add(2 * v + 1, tl, tm, l, r, a);
else if(l > tm)
add(2 * v + 2, tm+1, tr, l, r, a);
else {
add(2 * v + 1, tl, tm, l, tm, a);
add(2 * v + 2, tm + 1, tr, tm + 1, r, a);
}
st[v].stat[0] = st[2 * v + 1].stat[0] + st[2 * v + 2].stat[0];
st[v].stat[1] = st[2 * v + 1].stat[1] + st[2 * v + 2].stat[1];
}
void add(int s, int p, array<int, 2> a) {
while(anc[p] != anc[s]) {
add(0, 0, N - 1, pos[anc[s]], pos[s], a);
s = par[anc[s]];
}
add(0, 0, N - 1, pos[p], pos[s], a);
}
int cat(int v) {
--v;
flip(v);
hut[v]=0;
if(!v) {
array<int, 2> K = val(0);
ans -= min(K[0], K[1]);
ans += K[1];
return ans;
}
int O = get_loc(par[v]);
if(O == -1) {
array<int, 2> K = val(0), C = val(v);
ans -= min(K[0], K[1]);
add(par[v], 0, array<int, 2>{1-C[0], -C[1]});
K[0] -= C[0] - 1;
K[1] -= C[1];
ans += min(K[0], K[1]) + C[1];
return ans;
}
array<int, 2> C = val(v);
add(par[v], O, {1-C[0], -C[1]});
if(hut[O]) {
ans -= C[0];
ans += C[1] + 1;
}
return ans;
}
int dog(int v) {
--v;
flip(v);
hut[v]=1;
if(!v) {
array<int, 2> K = val(0);
ans -= min(K[0], K[1]);
ans += K[0];
return ans;
}
int O = get_loc(par[v]);
if(O == -1) {
array<int, 2> K = val(0), C = val(v);
ans -= min(K[0], K[1]);
add(par[v], 0, array<int, 2>{-C[0], 1-C[1]});
K[0] -= C[0];
K[1] -= C[1] - 1;
ans += min(K[0], K[1]) + C[0];
return ans;
}
array<int, 2> C = val(v);
add(par[v], O, {-C[0], 1-C[1]});
if(!hut[O]) {
ans -= C[1];
ans += C[0] + 1;
}
return ans;
}
int neighbor(int v) {
--v;
flip(v);
array<int, 2> C = val(v);
ans -= C[hut[v] ^ 1];
if(!v) {
ans += min(C[0], C[1]);
return ans;
}
int O = get_loc(par[v]);
if(O == -1) {
array<int, 2> K = val(0);
ans -= min(K[0], K[1]);
add(par[v], 0, array<int, 2>{C[0] - !hut[v], C[1] - hut[v]});
K[0] += C[0] - !hut[v];
K[1] += C[1] - hut[v];
ans += min(K[0], K[1]);
return ans;
}
if(hut[v] != hut[O])
--ans;
add(par[v], O, array<int, 2>{C[0] - (!hut[v]), C[1] - (hut[v])});
ans += C[hut[O] ^ 1];
return ans;
}/*
int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
int N=readInt();
std::vector<int> A(N-1),B(N-1);
for(int i=0;i<N-1;i++)
{
A[i]=readInt();
B[i]=readInt();
}
int Q;
assert(scanf("%d",&Q)==1);
std::vector <int> T(Q),V(Q);
for(int i=0;i<Q;i++)
{
T[i]=readInt();
V[i]=readInt();
}
initialize(N,A,B);
std::vector<int> res(Q);
for(int j=0;j<Q;j++)
{
if(T[j]==1) res[j]=cat(V[j]);
else if(T[j]==2) res[j]=dog(V[j]);
else res[j]=neighbor(V[j]);
}
for(int j=0;j<Q;j++)
printf("%d\n",res[j]);
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
