(color{#0066ff}{ 题目描述 })
给你一棵n个点的树，编号1~n。每个点可以是黑色，可以是白色。初始时所有点都是黑色。下面有两种操作请你操作给我们看：
0 u：询问有多少个节点v满足路径u到v上所有节点（包括）都拥有相同的颜色
1 u：翻转u的颜色
(color{#0066ff}{输入格式})
一行一个整数n
接下来n-1行，每行两个整数表示一条边
接下来一行一个整数m表示操作次数
接下来m行，每行两个整数分别表示操作类型和被操作节点
(color{#0066ff}{输出格式})
对每个询问操作输出相应的结果
(color{#0066ff}{输入样例})
5
1 2
1 3
1 4
1 5
3
0 1
1 1
0 1
(color{#0066ff}{输出样例})
5
1
(color{#0066ff}{数据范围与提示})
对所有数据，(1leq n leq 10^5)，(1leq m leq 10^5)
(color{#0066ff}{ 题解 })
容易想到，开两个LCT分别维护黑白两种颜色
然后修改颜色的时候，暴力cut相邻的边，link相邻的边
然而。。。存在一种东东叫菊花图。。。
显然很容易就被Hack掉了
正常LCT的题目中，如果有边权，我们肯定是边权转到点权上，这样才好维护
然而。。。本题就是与众不同，他要把点权转到边权上！
把每个点的点权转到它与父亲的边上，特别的，开一个0号节点，(0-1)存的是1的点权
然后询问的联通块即为所在联通块根的siz-1，注意，根的颜色跟其它点不同
因为根父亲的边不在这里！
因此仍然是LCT维护子树大小即可
对于改变颜色的问题，发现只需要断一条边即可
所以复杂度就保证了
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 1e5 + 10;
struct LCT {
protected:
struct node {
node *ch[2], *fa;
int siz, tot;
node(int siz = 0, int tot = 1): siz(siz), tot(tot) { ch[0] = ch[1] = fa = NULL; }
void upd() {
tot = siz + 1;
if(ch[0]) tot += ch[0]->tot;
if(ch[1]) tot += ch[1]->tot;
}
bool ntr() { return fa && (fa->ch[0] == this || fa->ch[1] == this); }
bool isr() { return fa->ch[1] == this; }
}pool[maxn];
void rot(node *x) {
node *y = x->fa, *z = y->fa;
bool k = x->isr(); node *w = x->ch[!k];
if(y->ntr()) z->ch[y->isr()] = x;
(x->ch[!k] = y)->ch[k] = w;
(y->fa = x)->fa = z;
if(w) w->fa = y;
y->upd(), x->upd();
}
void splay(node *o) {
while(o->ntr()) {
if(o->fa->ntr()) rot(o->isr() ^ o->fa->isr()? o : o->fa);
rot(o);
}
}
void access(node *x) {
for(node *y = NULL; x; x = (y = x)->fa) {
splay(x);
if(x->ch[1]) x->siz += x->ch[1]->tot;
if((x->ch[1] = y)) x->siz -= y->tot;
x->upd();
}
}
node *findroot(node *o) {
access(o), splay(o);
while(o->ch[0]) o = o->ch[0];
return splay(o), o;
}
public:
void link(int l, int r) {
node *x = pool + l, *y = pool + r;
access(x), splay(x);
x->fa = y;
access(y), splay(y);
y->siz += x->tot;
y->upd();
}
void cut(int l, int r) {
node *x = pool + l;
access(x), splay(x);
x->ch[0] = x->ch[0]->fa = NULL;
x->upd();
}
int query(int p) {
node *o = findroot(pool + p);
return o->ch[1]->tot;
}
}s[2];
struct node {
int to;
node *nxt;
node(int to = 0, node *nxt = NULL): to(to), nxt(nxt) {}
};
node *head[maxn];
int n, m, f[maxn], col[maxn];
void add(int from, int to) {
head[from] = new node(to, head[from]);
}
void dfs(int x, int fa) {
f[x] = fa;
s[1].link(x, fa);
for(node *i = head[x]; i; i = i->nxt)
if(i->to != fa)
dfs(i->to, x);
}
int main() {
n = in();
int x, y;
for(int i = 1; i <= n; i++) col[i] = 1;
for(int i = 1; i < n; i++) x = in(), y = in(), add(x, y), add(y, x);
dfs(1, 0);
for(m = in(); m --> 0;) {
x = in(), y = in();
if(x == 0) printf("%d
", s[col[y]].query(y));
if(x == 1) s[col[y]].cut(y, f[y]), s[col[y] ^= 1].link(y, f[y]);
}
return 0;
}