[SPOJ-QTREE6]Query on a tree VI 题解
![[SPOJ-QTREE6]Query on a tree VI 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180320b.jpg)
题目地址：洛谷：【SP16549】QTREE6 – Query on a tree VI – 洛谷、SPOJ：SPOJ.com – Problem QTREE6
SPOJ QTREE系列：
- [SPOJ-QTREE]Query on a tree 题解（树链剖分）
- [SPOJ-QTREE2]Query on a tree II 题解（树链剖分）
- [SPOJ-PT07J]Query on a tree III 题解（主席树）
- [SPOJ-QTREE3]Query on a tree again! 题解（树链剖分）
- [SPOJ-QTREE4]Query on a tree IV 题解（点分治/边分治）
- [SPOJ-QTREE5]Query on a tree V 题解（边分治）
- [SPOJ-QTREE6]Query on a tree VI 题解（LCT）
- [SPOJ-QTREE7]Query on a tree VII 题解（LCT）
题目描述
You are given a tree (an acyclic undirected connected graph) with n nodes. The tree nodes are numbered from 1 to n. Each node has a color, white or black. All the nodes are black initially. We will ask you to perform some instructions of the following form:
- 0 u: ask for how many nodes are connected to u, two nodes are connected if all the node on the path from u to v (inclusive u and v) have the same color.
- 1 u: toggle the color of u (that is, from black to white, or from white to black).
给一棵树，最初点全是黑色的，操作：1.询问到u路径颜色相同的点有多少个2.改变颜色
输入输出格式
输入格式：
The first line contains a number n that denotes the number of nodes in the tree (1 ≤ n ≤ 10^5). In each of the following n-1 lines, there will be two numbers (u, v) that describes an edge of the tree (1 ≤ u, v ≤ n). The next line contains a number m denoting number of operations we are going to process (1 ≤ m ≤ 10^5). Each of the following m lines describe an operation (t, u) as we mentioned above(0 ≤ t ≤ 1, 1 ≤ u ≤ n).
输出格式：
For each query operation, output the corresponding result.
输入输出样例
输入样例#1：
5 1 2 1 3 1 4 1 5 3 0 1 1 1 0 1
输出样例#1：
5 1
输入样例#2：
7 1 2 1 3 2 4 2 5 3 6 3 7 4 0 1 1 1 0 2 0 3
输出样例#2：
7 3 3
题解
参考资料：【Qtree】Query on a tree系列LCT解法 – CSDN博客
本题还是可以用边分……等等这题边分我做不动了，用的LCT。
我们考虑搞两棵LCT对应黑和白色的点构成的树。这样其实查询就变成了某一棵树上的子树大小查询。这个可以用子树信息LCT方便地维护。具体来说，就是统计一下跟当前点相连的轻边子树大小和Splay子树大小加起来。access的时候边合并Splay边更新轻边子树大小即可。
但是如果改变颜色的时候强行切边，有可能被菊花图卡掉。我们考虑把原树拉成一棵有根树，只切该点和父亲的边，这样，这棵LCT就满足所有儿子肯定同色，但是这个父亲可以跟儿子不同色这样的性质。我们在统计答案的时候找到子树根，然后看看子树根是否和儿子的颜色一致，不一致就取儿子的答案即可。
有一个小优化，可以DFS建树，把原树的边建成LCT上的轻边就好。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <algorithm>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 100005, INF = 1e9;
struct Edge {
int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], ecnt, fa[MAXN], col[MAXN];
inline void addedge(int u, int v, int w) {
gra[ecnt] = Edge {v, w, head[u]}; head[u] = ecnt++;
}
struct LCT {
struct LCTNode {
int ch[2], fa, siz, s;
bool rev;
} lct[MAXN];
inline bool isleft(int p) {
return lct[lct[p].fa].ch[0] == p;
}
inline bool isroot(int p) {
register int fa = lct[p].fa;
return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}
inline void update(int p) {
register int ls = lct[p].ch[0], rs = lct[p].ch[1];
lct[p].siz = lct[p].s + lct[ls].siz + lct[rs].siz + 1;
}
inline void reverse(int p) {
std::swap(lct[p].ch[0], lct[p].ch[1]);
lct[p].rev ^= 1;
}
inline void pushdown(int p) {
register int ls = lct[p].ch[0], rs = lct[p].ch[1];
if(lct[p].rev) {
if(ls) reverse(ls);
if(rs) reverse(rs);
lct[p].rev ^= 1;
}
}
int sta[MAXN], stop;
inline void pushto(int p) {
stop = 0;
while(!isroot(p)) {
sta[stop++] = p;
p = lct[p].fa;
}
pushdown(p);
while(stop) {
pushdown(sta[--stop]);
}
}
inline void rotate(int p) {
register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
lct[p].ch[!t] = fa; lct[fa].fa = p;
update(fa);
}
inline void splay(int p) {
pushto(p);
for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
}
update(p);
}
inline void access(int p) {
for(register int q = 0; p; q = p, p = lct[p].fa) {
splay(p);
if(lct[p].ch[1]) lct[p].s += lct[lct[p].ch[1]].siz;
if(q) lct[p].s -= lct[q].siz;
lct[p].ch[1] = q;
update(p);
}
}
inline void makert(int p) {
access(p);
splay(p);
reverse(p);
}
inline int findrt(int p) {
access(p);
splay(p);
while(lct[p].ch[0]) p = lct[p].ch[0];
return p;
}
inline void link(int u) {
access(fa[u]);
splay(fa[u]);
splay(u);
lct[fa[u]].ch[1] = u;
lct[u].fa = fa[u];
update(fa[u]);
}
inline void cut(int u) {
access(u);
splay(u);
lct[u].ch[0] = lct[lct[u].ch[0]].fa = 0;
update(u);
}
inline int query(int u) {
int c = col[u];
u = findrt(u);
splay(u);
return col[u] == c ? lct[u].siz : lct[lct[u].ch[1]].siz;
}
} L[2];
inline void dfs(int u, int f) {
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(v == f) continue;
fa[v] = L[0].lct[v].fa = u;
dfs(v, u);
L[0].lct[u].s += L[0].lct[v].siz;
}
L[0].update(u);
}
int n, q, ut, vt, op;
int main() {
memset(head, -1, sizeof(head));
n = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint();
addedge(ut, vt, 1);
addedge(vt, ut, 1);
}
dfs(1, 0);
q = readint();
while(q--) {
op = readint(); ut = readint();
if(!op) {
printf("%d\n", L[col[ut]].query(ut));
} else {
if(fa[ut]) {
L[col[ut]].cut(ut);
L[col[ut] ^ 1].link(ut);
}
col[ut] ^= 1;
}
}
return 0;
}
