https://www.luogu.com.cn/problem/SP16549
LCT维护子树大小经典题
多
记
录
一
个
s
i
[
x
]
表
示
非
实
边
儿
子
的
子
树
大
小
和
多记录一个si[x]表示非实边儿子的子树大小和
多记录一个si[x]表示非实边儿子的子树大小和
维护也很方便,直接看代码吧
注意!!写LCT断边的时候不要直接写连等,这是从右到左赋值的(调了一上午)
没啥细节
code:
#include<bits/stdc++.h>
#define N 100050
#define I inline
using namespace std;
I int read() {
int x = 0;
char ch = getchar();
for(; ch < '0' || ch > '9'; ) ch = getchar();
for(; ch >= '0' && ch <= '9'; ) x = (x << 3) + (x << 1) + (ch - 48), ch = getchar();
return x;
}
struct edge {
int v, nxt;
} e[N << 1];
int p[N], eid, Fa[N];
I void init() {
memset(p, -1, sizeof p);
eid = 0;
}
I void insert(int u, int v) {
e[eid].v = v;
e[eid].nxt = p[u];
p[u] = eid ++;
}
#define ls ch[x][0]
#define rs ch[x][1]
struct LCT {
int fa[N], ch[N][2], s[N], si[N];
I void init(int n) { for(int i = 1; i <= n + 1; i ++) s[i] = 1; }
I void update(int x) {
s[x] = s[ls] + s[rs] + si[x] + 1;
}
I int nrt(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
I int get(int x) {
return ch[fa[x]][1] == x;
}
I void rotate(int x) {
int f = fa[x], gf = fa[f], k = get(x);
if(nrt(f)) ch[gf][get(f)] = x; fa[x] = gf;
ch[f][k] = ch[x][!k], fa[ch[x][!k]] = f;
ch[x][!k] = f, fa[f] = x;
update(f), update(x);
}
I void splay(int x) {
int f = fa[x];
while(nrt(x)) { //printf("%d %d %d\n", x, f, fa[1]);
if(nrt(f)) rotate(get(f) == get(x)? f : x);
rotate(x);
f = fa[x];
if(f == x) exit(1);
}
}
I void access(int x) {
for(int y = 0; x; y = x, x = fa[x]) {
splay(x);
si[x] += s[rs];
rs = y;
si[x] -= s[rs];
}
}
I int findroot(int x) {
access(x), splay(x);
while(ls) x = ls;
splay(x); return x;
}
I void link(int x) {
splay(x);
int y = Fa[x];// printf(" %d %d\n", x, y);
fa[x] = y;
access(y), splay(y);
si[y] += s[x]; s[y] += s[x];
update(y);
}
I void cut(int x) {
access(x), splay(x);
fa[ls] = 0;//这里不要写连等!!!!
ls = 0;
update(x);
}
} t[2];
I void dfs(int u) {
t[0].link(u);
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v;
if(v == Fa[u]) continue;
Fa[v] = u; dfs(v);
}
}
int n, m, col[N];
int main() {
init();
n = read();
for(int i = 1; i < n; i ++) {
int u, v;
u = read(), v = read();
insert(u, v), insert(v, u);
}
Fa[1] = n + 1;
t[0].init(n), t[1].init(n);
dfs(1);
// for(int i = 1; i <= n; i ++) t[0].link(i);
m = read();
while(m --) {
int o, x;
o = read(), x = read();
if(o == 1) t[col[x]].cut(x), t[col[x] ^= 1].link(x);
else {
int rt = t[col[x]].findroot(x);
printf("%d\n", t[col[x]].s[t[col[x]].ch[rt][1]]);
}
}
return 0;
}
/*
4
1 2
1 3
3 4
2
1 3
1 3
*/