题目地址：洛谷：【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;
}