题解
老年选手的代码康复计划QAQ
这题又没一遍A，难受
每个节点维护这个节点子树内联通块的大小
维护所有节点轻儿子的(g[u][0])表示所有轻儿子白色的联通块总数
(g[u][1])表示所有轻儿子黑色联通块总数
更新一个点为新颜色的时候，是(g[u][c[u] ^ 1] + 1)再加上重儿子价值（如果修改后颜色相同
然后我们向上更新，修改到和父亲节点颜色相同的最浅的节点
如果改后颜色和父亲颜色不同，那么这些点都减去原来的值
否则都加上新值
然后在经过轻边的时候顺带维护一下(g)即可
对于找颜色相同的最浅节点，用线段树维护一个区间颜色是否相同即可
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('
')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M;
struct node {
int to,next;
}E[MAXN * 2];
int sumE,head[MAXN],c[MAXN];
int dfn[MAXN],son[MAXN],siz[MAXN],top[MAXN],dep[MAXN],fa[MAXN],idx,seq[MAXN];
int g[MAXN][2];
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
void dfs1(int u) {
dep[u] = dep[fa[u]] + 1;
siz[u] = 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u]) {
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u] && v != son[u]) {
g[u][1] += siz[v];
}
}
}
void dfs2(int u) {
dfn[u] = ++idx;seq[idx] = u;
if(!top[u]) top[u] = u;
if(son[u]) {top[son[u]] = top[u];dfs2(son[u]);}
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u] && v != son[u]) dfs2(v);
}
}
namespace seg_tr {
struct node {
int L,R;
int val,lz;
bool sc,col;
}tr[MAXN * 4];
#define lc(u) u << 1
#define rc(u) u << 1 | 1
#define val(u) tr[u].val
#define lz(u) tr[u].lz
#define sc(u) tr[u].sc
#define col(u) tr[u].col
void addlz(int u,int v) {
val(u) += v;lz(u) += v;
}
void push_down(int u) {
if(tr[u].lz) {
addlz(lc(u),tr[u].lz);
addlz(rc(u),tr[u].lz);
}
tr[u].lz = 0;
}
void update(int u) {
if(sc(lc(u)) && sc(rc(u)) && !(col(lc(u)) ^ col(rc(u)) ) ) {
sc(u) = 1;col(u) = col(lc(u));
}
else sc(u) = 0;
}
void build(int u,int l,int r) {
tr[u].L = l;tr[u].R = r;
if(l == r) {
tr[u].sc = 1;tr[u].col = c[seq[l]];
tr[u].val = siz[seq[l]];tr[u].lz = 0;
return;
}
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
update(u);
}
int query(int u,int p) {
if(tr[u].L == tr[u].R) return tr[u].val;
push_down(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(p <= mid) return query(lc(u),p);
else if(p > mid) return query(rc(u),p);
}
void add(int u,int l,int r,int v) {
if(tr[u].L == l && tr[u].R == r) {addlz(u,v);return;}
push_down(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(r <= mid) add(lc(u),l,r,v);
else if(l > mid) add(rc(u),l,r,v);
else {
add(lc(u),l,mid,v);
add(rc(u),mid + 1,r,v);
}
}
void change(int u,int p,int v,bool on) {
if(tr[u].L == tr[u].R) {
tr[u].val = v;
tr[u].col = on;
return;
}
push_down(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(p <= mid) change(lc(u),p,v,on);
else change(rc(u),p,v,on);
update(u);
}
int query_sc(int u,int l,int r) {
if(tr[u].L == l && tr[u].R == r) return tr[u].sc;
push_down(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(r <= mid) return query_sc(lc(u),l,r);
else if(l > mid) return query_sc(rc(u),l,r);
else {
return query_sc(lc(u),l,mid) && query_sc(rc(u),mid + 1,r) && c[seq[mid]] == c[seq[mid + 1]];
}
}
int Query(int p) {
return query(1,dfn[p]);
}
void Add(int l,int r,int v) {
add(1,l,r,v);
}
void Change(int p,int v,bool on) {
change(1,dfn[p],v,on);
}
bool Query_sc(int l,int r) {
return query_sc(1,l,r);
}
}
int Find_same_color(int u) {
while(1) {
if(seg_tr::Query_sc(dfn[top[u]],dfn[u])) {
if(top[u] == 1) return 1;
if(c[fa[top[u]]] != c[u]) return top[u];
u = fa[top[u]];
}
else {
int L = dfn[top[u]] + 1,R = dfn[u];
while(L < R) {
int mid = (L + R) >> 1;
if(seg_tr::Query_sc(mid,dfn[u])) R = mid;
else L = mid + 1;
}
return seq[L];
}
}
}
void Change_Path(int u,int v,int d) {
while(top[u] != top[v]) {
seg_tr::Add(dfn[top[u]],dfn[u],d);
g[fa[top[u]]][c[top[u]]] += d;
u = fa[top[u]];
}
seg_tr::Add(dfn[v],dfn[u],d);
if(v == top[u]) g[fa[v]][c[v]] += d;
}
void Init() {
read(N);
int u,v;
for(int i = 1 ; i <= N ; ++i) c[i] = 1;
for(int i = 1 ; i < N ; ++i) {
read(u);read(v);
add(u,v);add(v,u);
}
dfs1(1);dfs2(1);
seg_tr::build(1,1,N);
}
void Solve() {
read(M);
int op,u;
for(int i = 1 ; i <= M ; ++i) {
read(op);read(u);
if(!op) {
out(seg_tr::Query(Find_same_color(u)));enter;
}
else {
int nv = 1 + g[u][c[u] ^ 1] + (son[u] && c[son[u]] == (c[u] ^ 1) ? seg_tr::Query(son[u]) : 0);
int ov = seg_tr::Query(u);
if(u == 1) {
seg_tr::Change(u,nv,c[u] ^ 1);c[u] ^= 1;
}
else {
if(u == top[u]) {
g[fa[u]][c[u]] -= ov;
g[fa[u]][c[u] ^ 1] += nv;
}
int t = Find_same_color(fa[u]);
if(c[fa[u]] == c[u]) Change_Path(fa[u],t,-ov);
else Change_Path(fa[u],t,nv);
seg_tr::Change(u,nv,c[u] ^ 1);c[u] ^= 1;
}
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
return 0;
}