难度：NOI/NOI+/CTSC

题目描述

        计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。
        SHOI 组织由若干个 SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。每个SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞；并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有0和1两种。每个 SHOI 细胞根据三个输入端中0和1信号的多寡输出较多的那一种。
        现在给出了一段 SHOI 组织的信息,以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。

输入输出格式

输入格式：

        输入的第一行包含一个整数 n。表示 SHOI 组织的总细胞个数。SHOI 细胞由 1~n 编号,编号为 1 的是根细胞。
        从第二行开始的n行,每行三个整数$x_1, x_2, x_3$,分别表示编号为 1~n 的 SHOI 细胞的树突连接。$1 < x_i \leq n$，表示连向编号为 $x_i$的细胞的轴突, $n < x_i \leq 3n+1$表示连向编号为 $x_i$的外界输入。输入数据保证给出的SHOI 组织是合法的，且所有的 $x_i$两两不同。
        接下来一行包含2n+1个0/1的整数,表示初始时的外界输入。
        第n+3行有一个整数q,表示总操作数。
        之后q行每行一个整数x,表示编号为x的外界输入发生了变化。

输出格式：

        输出q行，每行一个整数,对应第i次外界输入变化后的根细胞的输出。

输入输出样例

Sample input

3
2 3 4
5 6 7
8 9 10
0 0 0 0 1 1 1
5
4
4
5
6
8

Sample output

1
0
0
1
1

说明

        对于100%的数据，$n \leq 500000, q \leq 500000$。

题解

        难度较大的LCT应用题。思路很巧妙，强烈推荐。
        注意到每一次修改都会使从叶子结点开始向根结点的一段序列发生改变。规定每一个点的点权为其来自子结点的1的数目，这样点权就有0~3四种情况。并且可以发现如果某个叶子结点的值从0变为1，则向上连续一段点权为1的点将连锁发生改变；从1变为0则向上连续一段点权为2的点将连锁发生改变。总结起来，如果从0变为1，则向上第一个不为1的点到叶子结点的点权都需要修改；从1变为0，则向上第一个不为2的点到叶子结点的点权都需要修改。这样问题简化为如何维护树链上点权的问题，可以用LCT搞出来。
        如果用朴素LCT写法，会发现翻转时不容易维护信息。因此可以采用非换根式的写法，一开始便指定1为根结点，之后不再更换。
        定义v[x]为点权，num[x][i]表示以x结点为根的splay树上最深的不为i的点的编号，plusTAG为加法懒标记。这样可以写出函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
inline void pushr(int x, int y) {//以x为根的树上结点点权加上y
    if (x) {
        v[x] += y, plusTAG[x] += y;//更新点权，打上标记
        if (y > 0)for (int i = 3; i >= 0; i--)num[x][i] = (i - y >= 0 ? num[x][i - y] : 0);//更新num
        else if (y < 0)for (int i = 0; i < 4; i++)num[x][i] = (i - y <= 3 ? num[x][i - y] : 0);
    }
}

inline void pushdown(int x) {//下压加法懒标记，这里没有翻转标记
    if (plusTAG[x])pushr(son[x][0], plusTAG[x]), pushr(son[x][1], plusTAG[x]), plusTAG[x] = 0;
}

inline void update(int x) {//更新信息
    if (v[x] == 1) {
        if (num[son[x][1]][1] == 0)num[x][1] = num[son[x][0]][1];//没有右儿子，去左儿子找
        else num[x][1] = num[son[x][1]][1];//继承右儿子
    } else {
        if (num[son[x][1]][1] == 0)num[x][1] = x;//右儿子没有，则x本身就是
        else num[x][1] = num[son[x][1]][1];
    }
    if (v[x] == 2) {
        if (num[son[x][1]][2] == 0)num[x][2] = num[son[x][0]][2];
        else num[x][2] = num[son[x][1]][2];
    } else {
        if (num[son[x][1]][2] == 0)num[x][2] = x;
        else num[x][2] = num[son[x][1]][2];
    }
}


        这样就是基本的链上修改操作。下面考虑在不换根的情况下如何建立LCT。
        考虑到点的关系是按照继承顺序给出的，可以直接如下修改：
1
2
3
4
5
6
7
for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &x), add(x, i), add(i, x);//这里是链式前向星存图使用的
            if (x > n)to[x - n] = i;//对于大于n的结点，记录一下其父结点，即输出结点
            else fa[x] = i;//LCT构造使用，直接虚边相连
        }
    }

        再然后，DFS出每一个点的初始点权，容易知道此时所有点独立成为一棵splay树，我们先建树再单独修改每一个点的点权是没有问题的。
        下面的查询修改操作就是重点：
1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 1; i <= q; i++) {
        scanf("%d", &x);
        if (v[x] == 3) {//我这里规定叶子结点为1权值就是3，为0就是0
            v[x] = 0;
            access(to[x - n]), splay(to[x - n]), access(realF[num[to[x - n]][2]]), splay(to[x - n]);//realF为原树中的父结点，DFS时候求出
            pushr(to[x - n], -1);
        } else {
            v[x] = 3;
            access(to[x - n]), splay(to[x - n]), access(realF[num[to[x - n]][1]]), splay(to[x - n]);
            pushr(to[x - n], 1);
        }
        splay(1), printf("%d\n", v[1] > 1);
    }

        上面代码中演示了如何在不换根的情况下把一条链剖出来。首先access到叶子结点，再splay，然后将其树上第一个不为1(2)的点的父结点access出来，剩下的就是我们需要的树链了。这里再进行一步splay，然后更新结点信息。
        查询时，先splay(1)，然后输出结果即可。我们在讨论LCT的文章末尾曾提及，split出来的splay树，其根结点信息必然是经过更新的。这里根就是1，所以makeRoot(1)和access(1)本质上是没有效果的，因此这里一步splay就可以更新信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>

#define N 500005

using namespace std;

int n, q, son[N][2], fa[N], sta[N], v[N * 3], plusTAG[N], to[N << 1 | 1], realF[N];
int num[N][3];
struct Edge {
    int to, next;
} edge[N * 6];
int head[N * 3], cnt = 1;

inline void add(int x, int y) {
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void pushr(int x, int y) {
    if (x) {
        v[x] += y, plusTAG[x] += y;
        if (y > 0)for (int i = 3; i >= 0; i--)num[x][i] = (i - y >= 0 ? num[x][i - y] : 0);
        else if (y < 0)for (int i = 0; i < 4; i++)num[x][i] = (i - y <= 3 ? num[x][i - y] : 0);
    }
}

inline void pushdown(int x) {
    if (plusTAG[x])pushr(son[x][0], plusTAG[x]), pushr(son[x][1], plusTAG[x]), plusTAG[x] = 0;
}

inline void update(int x) {
    if (v[x] == 1) {
        if (num[son[x][1]][1] == 0)num[x][1] = num[son[x][0]][1];
        else num[x][1] = num[son[x][1]][1];
    } else {
        if (num[son[x][1]][1] == 0)num[x][1] = x;
        else num[x][1] = num[son[x][1]][1];
    }
    if (v[x] == 2) {
        if (num[son[x][1]][2] == 0)num[x][2] = num[son[x][0]][2];
        else num[x][2] = num[son[x][1]][2];
    } else {
        if (num[son[x][1]][2] == 0)num[x][2] = x;
        else num[x][2] = num[son[x][1]][2];
    }
}

inline bool isNotRoot(int x) {
    return son[fa[x]][0] == x || son[fa[x]][1] == x;
}

inline int identify(int x) {
    return son[fa[x]][1] == x;
}

inline void change(int f, int s, int w) {
    fa[s] = f, son[f][w] = s;
}

inline void rotate(int x) {
    int f = fa[x], g = fa[f], i = identify(x), j = identify(f);
    if (!isNotRoot(f))fa[x] = g;
    else change(g, x, j);
    change(f, son[x][i ^ 1], i), change(x, f, i ^ 1), update(f), update(x);
}

inline void splay(int x) {
    int i = 0, y = x;
    sta[++i] = y;
    while (isNotRoot(y))sta[++i] = y = fa[y];
    while (i)pushdown(sta[i--]);
    while (isNotRoot(x)) {
        int f = fa[x];
        if (isNotRoot(f)) {
            if (identify(x) == identify(f))rotate(f);
            else rotate(x);
        }
        rotate(x);
    }
}

inline void access(int x) {
    for (int i = 0; x; x = fa[i = x])splay(x), son[x][1] = i, update(x);
}

void DFS(int x, int fa) {
    if (x > n)return;
    realF[x] = fa;
    for (int i = head[x]; i; i = edge[i].next)if (edge[i].to != fa)DFS(edge[i].to, x), v[x] += (v[edge[i].to] > 1);
}

int main() {
    int x;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &x), add(x, i), add(i, x);
            if (x > n)to[x - n] = i;
            else fa[x] = i;
        }
    }
    for (int i = 1; i <= (n << 1 | 1); i++)scanf("%d", &x), v[i + n] = (x ? 3 : 0);
    DFS(1, 0);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d", &x);
        if (v[x] == 3) {
            v[x] = 0;
            access(to[x - n]), splay(to[x - n]), access(realF[num[to[x - n]][2]]), splay(to[x - n]);
            pushr(to[x - n], -1);
        } else {
            v[x] = 3;
            access(to[x - n]), splay(to[x - n]), access(realF[num[to[x - n]][1]]), splay(to[x - n]);
            pushr(to[x - n], 1);
        }
        splay(1), printf("%d\n", v[1] > 1);
    }
    return 0;
}


        本题影射了LCT中结点的更新规律，并且有着不换根剖树链的黑科技操作，强烈推荐一做。