树剖可以把树上的信息映射到一条链上

树剖可以解决树上两点之间的快速(10 ^ 5左右)查询和修改问题…
其实树剖并不是一种算法…而更像一种思想…
毕竟剖完了还要用各种数据结构
建议学习之前先看看这个会有助于理解…
开完上面那个你应该知道: 一个节点的子树在DFS序列中是挨在一起的…
两个的思想差不多…都是把树上的值转换到序列上…然后就可以用一些喜闻乐见的数据结构或者DP来做惹…只不过转换的依据不同…一个是直接按照DFS序一个是按照子节点的多少…
树剖中经常用的是一种叫做 [轻重链剖分] 的东西…也就是说根据 [一个节点在他的兄弟中节点的多少] 来转换这颗树…先明确几个概念…

重儿子: siz[u]为v的子节点中siz值最大的, 那么u就是v的重儿子
轻儿子: v的其它子节点
重边: 点v与其重儿子的连边
轻边: 点v与其轻儿子的连边
重链: 由重边连成的路径
轻链: 轻边(一条轻边就是一条轻链)
链顶(top): 一条链(轻或重)中的的深度最小的节点
跳一条链(沿着一条链走): 把一个节点变成这个节点所在链的链顶的父亲

然后就可以把好好的一棵树分成几条轻链和几条重链
上面这些玩意一遍DFS就能求出来惹…对吧?
求这些不是白求的…求出来就有几个性质…

  1. 如果(v,u)为轻边, 则sum[u] * 2 <= sum[v];
  2. 从根到某一点的路径上轻链 or 重链的个数都不大于logn

证明…

  1. 显然如果一个子节点的sumsum[v], 比他父节点的sum值的一半还大的话这个子节点是不是就是重儿子了…?(兄弟节点的sum没有比v大的了)
  2. 也很显然…由 性质1 得…即使是都沿着轻链(一次只走一层)走(从上往下), 一次也可以减少一半的节点数…更别说重链一次就到链顶了呢…

e.g.1(传送至 Luogu)

那么怎么维护呢…因为重链包含的节点个数多…所以重链用一些高级的数据结构维护…轻链一共就俩节点还不是想怎么维护怎么维护 可以直接维护…
因为重链要用数据结构维护…而数据结构一般都是在序列上工作的…所以要让每一条重链上的所有节点 挨在一起, 所以普通的DFS序(一遍DFS)就不能解决问题了…

总结一下…树剖就是用一种标准(轻重), 把树分成几部分分别维护, 包含点多的部分就用数据结构维护, 包含点少的部分就直接暴力改…

所以例题的流程就是…

  1. DFS第一遍, 求出每一个节点的重儿子
  2. DFS第二遍, 遇到一个节点, 先遍历他的重儿子, 以保证重链在序列上是连续的一块
  3. 建树, 在DFS序列上建立一个数据结构
  4. 在数据结构上维护…

具体修改两点间的权重的话就是像倍增LCA一样…只不过LCA是一次往上跳1 << i个节点, 树剖是一次跳过一条链

复杂度…往上跳的话是logn的…然后加上数据结构一般也是logn的话…总的复杂度大概是两个log

然后做的几个题…

NOI2015 软件包管理 在DFS序列上维护一个能全部置0 / 1的线段树即可, 安装的时候就输出 [个点的深度 - 这个点到根上安装了几个包], 删除的时候就把子树置0即可 一遍过辣开心

SDOI2011 染色 维护一个区间上的 颜色块数 and 区间左侧的颜色 and 区间右侧的颜色 即可, 合并两个子区间的时候注意两个区间交界的颜色如果相同块数要 -= 1…注意可能需要卡常…注意细节…不要乱用别名…别名的别名可能会GG…

水果姐逛水果街Ⅲ 比较麻烦…见我的blog

苹果树 其实并不用剖分…因为没有查询两点间的权重所以直接在DFS序列上做就行…

没了
所以树剖的核心代码大概就是两个DFS wwwwwww
改天有空用树状数组写一下可能更快…

链剖就算告一段落了…接下来开坑网络流…

沙茶的 代码

例题1
注意取膜…不取膜卡30非常伤心…
加了一个end方便修改整个子树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = b; b = a; a = t;}
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)
#define INF (0x7ffffff)
#define LL long long

int root;
using namespace std;
struct tnode
{
    LL wei; // 节点权值
    int start; // 节点在 a 中第一次出现的位置
    int end; // 节点的子树全部遍历完后的位置
    int top; // 链顶
    int deep; // 节点深度
    int sum; // 子树节点个数
    int fa; // 节点的父亲
    int hs; // 节点的重儿子
} ta[MAXN];

struct node
{
    int le;
    int ri;
    LL zh;
    LL lazy;
} b[MAXN << 2];

struct edg
{
    int from;
    int to;
    int next;
} tb[MAXN << 1];
int cntb = 0;
int g[MAXN];

LL a[MAXN];
int cnts = 0;
int n;
LL mod;
LL cx(int, int, int);
void xg(int, int, int, LL);
void js(int, int, int);
void init(int, int);
void dfs(int);
void adn(int, int);
void solve(int, int, LL);
LL solve(int, int);
inline void push(int);
int main()
{
    int q;
    scanf("%d%d%d%lld", &n, &q, &root, &mod);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &ta[i].wei);
        ta[i].wei %= mod;
    }
    int srx, sry;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    ta[root].fa = root;
    ta[root].top = root;
    init(root, 1);
    dfs(root);
    js(1, 1, n);
    int sre, srz;
    for (int i = 1; i <= q; i++)
    {
        scanf("%d", &sre);
        if (sre == 4)
        {
            scanf("%d", &srx);
            printf("%lld\n", cx(1, ta[srx].start, ta[srx].end));
        }
        else
        {
            scanf("%d%d", &srx, &sry);
            if (sre == 1)
            {
                scanf("%d", &srz);
                srz %= mod;
                solve(srx, sry, srz);
            }
            else if (sre & 1)
            {
                xg(1, ta[srx].start, ta[srx].end, sry);
            }
            else
            {
                printf("%lld\n", solve(srx, sry));
            }
        }
    }
    return 0;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le;
    b[dq].ri = ri;
    b[dq].lazy = 0;
    if (le == ri)
    {
        b[dq].zh = a[le];
    }
    else
    {
        int mi = (le + ri) >> 1;
        js(LS(dq), le, mi);
        js(RS(dq), mi + 1, ri);
        b[dq].zh = (b[LS(dq)].zh + b[RS(dq)].zh) % mod;
    }
}
void push(int dq)
{
    LL& x = b[dq].lazy;
    b[LS(dq)].lazy += x, b[RS(dq)].lazy += x;
    b[LS(dq)].lazy %= mod, b[RS(dq)].lazy %= mod;
    b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
    b[LS(dq)].zh %= mod;
    b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
    b[RS(dq)].zh %= mod;
    x = 0;
}
void xg(int dq, int le, int ri, LL zh)
{
    if (le > ri)
        return ;
    if(b[dq].lazy && b[dq].le != b[dq].ri)
        push(dq);
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].zh += (ri - le + 1) * zh;
        b[dq].zh %= mod;
        b[dq].lazy += zh;
        b[dq].lazy %= mod;
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
        {
            xg(RS(dq), le, ri, zh);
        }
        else if (ri <= mi)
        {
            xg(LS(dq), le, ri, zh);
        }
        else
        {
            xg(LS(dq), le, mi, zh);
            xg(RS(dq), mi + 1, ri, zh);
        }
        b[dq].zh = (b[LS(dq)].zh + b[RS(dq)].zh) % mod;
    }
}
LL cx(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].zh;
    }
    if(b[dq].lazy && b[dq].le != b[dq].ri)
        push(dq);
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
    {
        return cx(RS(dq), le, ri);
    }
    else if (ri <= mi)
    {
        return cx(LS(dq), le, ri);
    }
    else
    {
        return (cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri)) % mod;
    }
}
void adn(int fr, int to)
{
    tb[++cntb].next = g[fr];
    tb[cntb].from = fr;
    tb[cntb].to = to;
    g[fr] = cntb;
}

void init(int dq, int de)
{
    ta[dq].deep = de;
    ta[dq].sum = 1;
    int maxs = 0;
    int& hs = ta[dq].hs;
    hs = 0;
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, de + 1);
            ta[dq].sum += ta[tb[i].to].sum;
            if (ta[tb[i].to].sum > maxs)
            {
                maxs = ta[tb[i].to].sum;
                hs = tb[i].to;
            }
        }
    }
}

void dfs(int dq)
{
    ta[dq].start = ++cnts;
    a[cnts] = ta[dq].wei;
    if (ta[dq].hs)
    {
        ta[ta[dq].hs].top = ta[dq].top;
        dfs(ta[dq].hs);
    }
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    }
    ta[dq].end = cnts;
}

void solve(int x, int y, LL zh)
{
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep > ta[ta[y].top].deep)
        {
            swap(x, y);
        }
        xg(1, ta[ta[y].top].start, ta[y].start, zh);
        y = ta[ta[y].top].fa;
    }
    if (ta[x].deep < ta[y].deep)
        xg(1, ta[x].start, ta[y].start, zh);
    else
        xg(1, ta[y].start, ta[x].start, zh);
}

LL solve(int x, int y)
{
    LL re = 0;
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep > ta[ta[y].top].deep)
        {
            swap(x, y);
        }
        re += cx(1, ta[ta[y].top].start, ta[y].start);
        re %= mod;
        y = ta[ta[y].top].fa;
    }
    if (ta[x].deep < ta[y].deep)
        re += cx(1, ta[x].start, ta[y].start);
    else
        re += cx(1, ta[y].start, ta[x].start);
    return re % mod;
}

/*
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
*/

软件包管理

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXQ (100000 + 5)
#define MAXE (20 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)
using namespace std;
const int root = 1;

struct edg
{
    int from;
    int to;
    int next;
}tb[MAXN << 1];
int cntb = 0;
int g[MAXN];

struct node
{
    int le;
    int ri;
    int zh;
    int lazy;
}b[MAXN << 2];

struct tnode
{
    int top;
    int fa;
    int deep;
    int start;
    int end;
    int hs;
    int sum;
}ta[MAXN];

int a[MAXN];
int cnts;

int n;
void js(int, int, int); // 
void xg(int, int, int, int); //
int cx(int, int, int); // 
void init(int, int); //
void dfs(int); //
int solve(int);
void adn(int, int); //
inline void push_down(int);
inline void push_up(int);
int main()
{
    scanf("%d", &n);
    int srx;
    for (int i = 2; i <= n; i++)
    {
        scanf("%d", &srx);
        ta[i].fa = srx + 1;
        adn(ta[i].fa, i);
    }
    ta[root].fa = root;
    init(root, 1);
    ta[root].top = root;
    dfs(root);
    js(1, 1, n);
    int q;
    scanf("%d", &q);
    char sre[MAXE];
    for (int i = 1; i <= q; i++)
    {
        scanf("%s%d", sre, &srx);
        ++srx;
        if (sre[0] == 'i')// install
        {
            printf("%d\n", ta[srx].deep - solve(srx)); // 计算 srx 到根的路径上安装了 x 个包, 用深度 - x, 并把 srx 到根上的点都置为 1
        }
        else // uninstall
        {

            printf("%d\n", cx(1, ta[srx].start, ta[srx].end));
            xg(1, ta[srx].start, ta[srx].end, 0); // 计算 srx 的子树中包的数量, 并把 srx 的子树全部置成 0
        }
    }
    return 0;
}
void adn(int from, int to)
{
    tb[++cntb].next = g[from];
    tb[cntb].from = from;
    tb[cntb].to = to;
    g[from] = cntb;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le;
    b[dq].ri = ri;
    b[dq].lazy = 0;
    if (le == ri)
    {
        b[dq].zh = a[le];
    }
    else
    {
        int mi = (le + ri) >> 1;
        js(LS(dq), le, mi);
        js(RS(dq), mi + 1, ri);
        push_up(dq);
    }
}
void xg(int dq, int le, int ri, int zh)
{
    if (le > ri)
        return ;
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].lazy = zh + 1;
        b[dq].zh = (ri - le + 1) * zh; 
        return ;
    }
    if (b[dq].lazy)
        push_down(dq);
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
    {
        xg(RS(dq), le, ri, zh);
    }
    else if (ri <= mi)
    {
        xg(LS(dq), le, ri, zh);
    }
    else
    {
        xg(LS(dq), le, mi, zh);
        xg(RS(dq), mi + 1, ri, zh);
    }
    push_up(dq);
}
int cx(int dq, int le, int ri)
{
    if (le > ri)
        return 0;
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].zh;
    }
    if (b[dq].lazy)
    {
        push_down(dq);
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
    {
        return cx(RS(dq), le, ri);
    }
    else if (ri <= mi)
    {
        return cx(LS(dq), le, ri);
    }
    else 
    {
        return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
    }
}
inline void push_down(int dq)
{
    int& x = b[dq].lazy;
    int y = x - 1;
    b[LS(dq)].lazy = b[RS(dq)].lazy = x;
    b[LS(dq)].zh = (b[LS(dq)].ri - b[LS(dq)].le + 1) * y;
    b[RS(dq)].zh = (b[RS(dq)].ri - b[RS(dq)].le + 1) * y;
    x = 0;
}
inline void push_up(int dq)
{
    b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}

/*
struct tnode
{
    int top;
    int fa;
    int deep;
    int start;
    int end;
    int hs;
    int sum;
}ta[MAXN];
*/

void init(int dq, int de)
{
    ta[dq].deep = de;
    ta[dq].sum = 1;
    int maxs = 0;
    int hs = 0;
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, de + 1);
            ta[dq].sum += ta[tb[i].to].sum;
            if (ta[tb[i].to].sum > maxs)
            {
                maxs = ta[tb[i].to].sum;
                hs = tb[i].to;
            }
        }
    }
    ta[dq].hs = hs;
}

/*
struct tnode
{
    int top;
    int fa; // ...
    int deep; // ...
    int start;
    int end;
    int hs; // ...
    int sum; // ...
}ta[MAXN];
*/

void dfs(int dq)
{
    ta[dq].start = ++cnts;
    if (ta[dq].hs)
    {
        ta[ta[dq].hs].top = ta[dq].top;
        dfs(ta[dq].hs);
    }
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].hs && tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    }
    ta[dq].end = cnts;
}
int solve(int x)
{
    int re = 0;
    while (ta[x].top != root)
    {
        re += cx(1, ta[ta[x].top].start, ta[x].start);
        xg(1, ta[ta[x].top].start, ta[x].start, 1);
        x = ta[ta[x].top].fa;
    }
    re += cx(1, ta[root].start, ta[x].start);
    xg(1, ta[root].start, ta[x].start, 1);
    return re;
}

/*
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
*/

染色…注意细节…


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define MAXQ (1000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define LL long long
#define swap(a, b) {int t = b; b = a; a = t;}
#define INF (0x7ffffff)
const int root = 1;
using namespace std;
struct node
{
    int le;
    int ri;
    LL col;
    int lec;
    int ric;
    int lazy;
}b[MAXN    << 2];
struct tnode
{
    int col;
    int hs;
    int fa;
    int top;
    int sum;
    int deep;
    int start;
    int end;
}ta[MAXN];
struct edg
{
    int from;
    int to;
    int next;
}tb[MAXN << 1];
int cntb = 0;
int g[MAXN];

int n;
int cnts = 0;
int a[MAXN];
void js(int, int, int); // done
void xg(int, int, int, int); // done
node cx(int, int, int); // done
inline void push_up(int);
inline void push_down(int);
void init(int, int); // done
void dfs(int); // done
void solve(int, int, int);
LL solve(int, int);
void adn(int, int);
int main()
{
//    freopen("in.in", "r", stdin);
//    freopen("wa.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
//    scanf("%d%d", &n, &q);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
//        scanf("%d", &ta[i].col);
        cin >> ta[i].col;
    }
    int srx, sry, srz;
    for (int i = 1; i < n; i++)
    {
//        scanf("%d%d", &srx, &sry);
        cin >> srx >> sry;
        adn(srx, sry);
        adn(sry, srx);
    }
    ta[root].fa = ta[root].top = root;
    init(root, 1);
    dfs(root);
    js(1, 1, n);
    char sre;
    for (int i = 1; i <= q; i++)
    {
        cin >> sre >> srx >> sry;
        if (sre == 'C')
        {
            cin >> srz;
            solve(srx, sry, srz);
        }
        else 
        {
            cout << solve(srx, sry) << endl;
        }
    }
    return 0;
}
void adn(int from, int to)
{
    tb[++cntb].next = g[from];
    tb[cntb].from = from;
    tb[cntb].to = to;
    g[from] = cntb;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le;
    b[dq].ri = ri;
    b[dq].lazy = 0;
    if (le == ri)
    {
        b[dq].lec = b[dq].ric = a[le];
        b[dq].col = 1;
    }
    else
    {
        int mi = (le + ri) >> 1;
        js(LS(dq), le, mi);
        js(RS(dq), mi + 1, ri);
        push_up(dq);
    }
}
node cx(int dq, int le, int ri)
{
    if (b[dq].lazy)
    {
        push_down(dq);
    }
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq];
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (ri <= mi)
        {
            return cx(LS(dq), le, ri);
        }
        else if (le > mi)
        {
            return cx(RS(dq), le, ri);
        }
        else
        {
            node lez = cx(LS(dq), le, mi), riz = cx(RS(dq), mi + 1, ri);
            node re;
            re.lec = lez.lec, re.ric = riz.ric;
            re.col = riz.col + lez.col - ((riz.lec == lez.ric) ? (1) : 0);
            return re;
        }
    }
}

/*
struct node
{
    int le;
    int ri;
    int col;
    int lec;
    int ric;
    int lazy;
}b[MAXN    << 1];
*/

void xg(int dq, int le, int ri, int co)
{
    if (b[dq].lazy)
    {
        push_down(dq);
    }
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].col = 1;
        b[dq].lec = b[dq].ric = b[dq].lazy = co;
    }
    else 
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (ri <= mi)
        {
            xg(LS(dq), le, ri, co);
        }
        else if (le > mi)
        {
            xg(RS(dq), le, ri, co);
        }
        else
        {
            xg(LS(dq), le, mi, co);
            xg(RS(dq), mi + 1, ri, co);
        }
        push_up(dq);
    }
}



inline void push_up(int dq)
{
    b[dq].lec = b[LS(dq)].lec, b[dq].ric = b[RS(dq)].ric;
    b[dq].col = b[RS(dq)].col + b[LS(dq)].col - ((b[RS(dq)].lec == b[LS(dq)].ric) ? (1) : 0);
}

/*
struct node
{
    int le;
    int ri;
    int col;
    int lec;
    int ric;
    int lazy;
}b[MAXN    << 1];
*/

inline void push_down(int dq)
{
    b[RS(dq)].lec = b[RS(dq)].ric = b[LS(dq)].lec = b[LS(dq)].ric =    b[RS(dq)].lazy = b[LS(dq)].lazy = b[dq].lazy;
    b[RS(dq)].col = b[LS(dq)].col = 1;
    b[dq].lazy = 0;
}

/*
struct tnode
{
    int col;
    int hs;
    int fa;
    int top;
    int sum;
    int deep;
    int start;
    int end;
}ta[MAXN];
*/

void init(int dq, int deep)
{
    ta[dq].deep = deep;
    ta[dq].sum = 1;
    int maxs = 0;
    int hs = 0;
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, deep + 1);
            ta[dq].sum += ta[tb[i].to].sum;
            if (ta[tb[i].to].sum > maxs)
            {
                maxs = ta[tb[i].to].sum;
                hs = tb[i].to;
            }
        }
    }
    ta[dq].hs = hs;
}

/*struct tnode
{
    int col; // done in main
    int hs; // done in init
    int fa; // done in init
    int top;
    int sum; // done in init
    int deep; // done in init
    int start;
    int end;
}ta[MAXN];
*/

void dfs(int dq)
{
    a[++cnts] = ta[dq].col;
    ta[dq].start = cnts;
    if (ta[dq].hs)
    {
        ta[ta[dq].hs].top = ta[dq].top;
        dfs(ta[dq].hs);
    }
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    }
    ta[dq].end = cnts;
}

void solve(int x, int y, int col)
{
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep)
        {
            swap(x, y);
        }
        xg(1, ta[ta[x].top].start, ta[x].start, col);
        x = ta[ta[x].top].fa;
    }
    if (ta[x].deep < ta[y].deep)
    {
        swap(x, y);
    }
    xg(1, ta[y].start, ta[x].start, col);
}
LL solve(int fr, int to)
{
    LL re = 0;
    node cxf, cxt;
    int lfc, ltc;
    lfc = ltc = -1;
    while (ta[fr].top != ta[to].top)
    {
        if (ta[ta[fr].top].deep < ta[ta[to].top].deep) // move to
        {
            cxt = cx(1, ta[ta[to].top].start, ta[to].start);
            re += cxt.col;
            re -= ((ltc == cxt.ric) ? (1) : (0));
            ltc = cxt.lec;
            to = ta[ta[to].top].fa;
        }
        else
        {
            cxf = cx(1, ta[ta[fr].top].start, ta[fr].start);
            re += cxf.col;
            re -= ((lfc == cxf.ric) ? (1) : (0));
            lfc = cxf.lec;
            fr = ta[ta[fr].top].fa;
        }
    }
    if (ta[fr].deep < ta[to].deep)
    {
        cxt = cx(1, ta[fr].start, ta[to].start);
        re += cxt.col;
        re -= ((cxt.ric == ltc) ? (1) : (0));
        ltc = cxt.lec;
    }
    else
    {
        cxf = cx(1, ta[to].start, ta[fr].start);
        re += cxf.col;
        re -= ((cxf.ric == lfc) ? (1) : (0));
        lfc = cxf.lec;
    }
    re -= ((lfc == ltc) ? (1) : (0));
    return re;
}

苹果树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)
#define INF (0x7ffffff)
const int root = 1;
using namespace std;
struct node
{
    int le;
    int ri;
    int zh;
}b[MAXN << 2];
struct edg
{
    int fr;
    int to;
    int next;
}tb[MAXN << 1];
int cntb = 0;
int g[MAXN];
struct tnode
{
    int wei;
    int hs;
    int sum;
    int deep;
    int start;
    int end;
    int fa;
    int top;
}ta[MAXN];

int cnts = 0;
int a[MAXN];
int n;
void adn(int, int);
void js(int, int, int);
void xg(int, int);
int cx(int, int, int);
void init(int, int);
void dfs(int);
void solve(int);
inline void push_up(int);
int main()
{
    cin >> n;
    int srx, sry;
    for (int i = 1; i < n; i++)
    {
        cin >> srx >> sry;
        adn(srx, sry);
        adn(sry, srx);
    }
    ta[root].fa = ta[root].top = root;
    init(root, 1);
    dfs(root);
    js(1, 1, n);
    int q;
    cin >> q;
    char sre;
    for (int i = 1; i <= q; i++)
    {
        cin >> sre >> srx;
        if (sre == 'C')
        {
            xg(1, ta[srx].start);
        }
        else
        {
            cout << cx(1, ta[srx].start, ta[srx].end) << endl;
        }
    }
    return 0;
}
void adn(int fr, int to)
{
    tb[++cntb].next = g[fr];
    tb[cntb].fr = fr;
    tb[cntb].to = to;
    g[fr] = cntb;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le;
    b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].zh = a[le];
    }
    else
    {
        int mi = (le + ri) >> 1;
        js(LS(dq), le, mi);
        js(RS(dq), mi + 1, ri);
        push_up(dq);
    }
}
void xg(int dq, int wz)
{
    if (b[dq].le == b[dq].ri)
    {
        if (b[dq].le == wz)
        {
            b[dq].zh = ((b[dq].zh) ? (0) : 1);
        }
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (wz <= mi)
            xg(LS(dq), wz);
        else if (wz > mi)
            xg(RS(dq), wz);
        push_up(dq);
    }
}
int cx(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].zh;
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
            return cx(RS(dq), le, ri);
        else if (ri <= mi)
            return cx(LS(dq), le, ri);
        else
            return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
    }
}
inline void push_up(int dq)
{
    b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}

/*
struct tnode
{
    int wei;
    int hs;
    int sum;
    int deep;
    int start;
    int end;
}ta[MAXN];
*/

void init(int dq, int de)
{
    ta[dq].deep = de;
    ta[dq].hs = 0;
    ta[dq].sum = ta[dq].wei = 1;
    int maxs = 0;
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, de + 1);
            ta[dq].sum += ta[tb[i].to].sum;
            if (ta[tb[i].to].sum > maxs)
                maxs = ta[tb[i].to].sum, ta[dq].hs = tb[i].to;
        }
    }
}

/*
struct tnode
{
    int wei; // ...done
    int hs; // done
    int sum; // ...done
    int deep; // ...done
    int start;
    int end; 
}ta[MAXN];
*/

void dfs(int dq)
{
    ta[dq].start = ++cnts;
    a[cnts] = ta[dq].wei;
    if (ta[dq].hs)
    {
        ta[ta[dq].hs].top = ta[dq].top;
        dfs(ta[dq].hs);
    }
    for (int i = g[dq]; i; i = tb[i].next)
    {
        if (ta[dq].fa != tb[i].to && tb[i].to != ta[dq].hs)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    }
    ta[dq].end = cnts;
}

By 码风奇特代码极长的头都快被剖开的 Cansult