[LCT刷题][树链信息维护] P4332 [SHOI2014]三叉神经树

写在前面

把黑题看成蓝题结果想了老半天感觉不对劲

本题对于理解$Splay$和$LCT$结构具有至关重要的意义，值得反复思考。

可能因为我比较菜

题目思路

题目给定一个类似神经网络的东西，每个节点都具有激活层、三输入单输出，输出由输入的$1$的个数决定，$1$比$0$多就输出$1$。每次修改一个外界输入，要求求根节点的输出。

首先考虑一个问题，修改外界输入对上级节点输出的影响究竟有几种：

1. 从叶子节点开始有一段连续的输入$1$的个数为$1$的节点
   不难发现，此时如果将$12$号节点修改为$1$，那么因此的改变到$3$号点(第一个非$1$点)终止，不会引起根节点的修改
2. 同样，从叶子节点开始有一段连续的输入$1$个数为$2$的节点，此时叶节点的改变只会影响到第一个非$2$点

那么就可以解决这个问题了，对于每个修改的叶子节点，找到向上首个非$1$/非$2$节点(对应叶节点$0\to 1$和$1\to 0$)。

考虑使用LCT维护这个信息，对每个节点记录两个变量$i{d}_1$和$i{d}_2$，分别表示沿当前点向上的第一个非$1$/非$2$点。然后每次修改前$Access(x)$再$Splay(x)$就可以将信息上传到$x$待修改的$x$节点上。

但是注意，这里的$x$节点并不是输入的那个叶子节点，而是它的父亲节点，因为叶子节点没有输入只有输出，修改是没有意义的。

那么问题就来了，信息该怎样上传到$x$节点呢？我们回想$LCT$的三个关键操作：$Rotate(x),Splay(x),Access(x)$，我们可以以上树为例来理解：

我们建树时全部连虚边(只连父不连子)，然后执行$Access(12)$，这时$1\sim 12$的点全部位于一条实链上，然后我们将$12$旋到根上，在这里需要注意，我们看一下$Rotate()$和$Splay()$两个函数：

void rotate(int x) {
    int y = f[x], z = f[y], k = get(x);
    if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
    ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
    ch[x][!k] = y, f[y] = x, f[x] = z;
    push_up(y); push_up(x);
}

void update(int x) {
    if(!isRoot(x)) update(f[x]);
    push_down(x);
}

void splay(int x) {
    update(x);
    for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]) {
        if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);
    }
    push_up(x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

每次$Rotate$后，我们会先更新原先的父亲节点的信息，再更新当前节点的信息。那么在一路将$12$旋到根的过程中，我们会将到根节点路径上的点旋到$x$的子树里，并将信息更新给正在旋转过程中的$x$。那么我们考虑如何能够找到我们需要的信息：向上首个非$1$/非$2$节点，那么这些信息一定存在于其父亲节点(此处的父亲节点指的是旋转前的父亲节点)的右子树(旋转后)(感性理解，$x$的左子树为深度严格小于$x$的节点，左子树首个节点的右子树在仍然满足深度严格小于$x$的同时深度继续增大)，因此我们优先从右子树继承信息，当右子树没有信息时判断当前节点是否满足，否则才从左子节点继承信息(此时更新的一般是$x$节点本身，而不是其父亲节点)。

此外，本题细节比较多，要仔细写。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 3e6 + 10;

int n = 0;

namespace LCT{
    struct Info{
        short in, out;
		int id1, id2, add_tag;
        void activate() { out = (in >= 2); }
    }tree[N];
    int ch[N][2], f[N], tag[N];
    
    #define ls ch[x][0]
    #define rs ch[x][1]

    inline void push_reverse(int x) { swap(ls, rs), tag[x] ^= 1; }

    inline void push_add(int x, int c) {
        tree[x].in += c;
        tree[x].add_tag += c;
        tree[x].activate();
        swap(tree[x].id1, tree[x].id2);
    }

    inline void push_down(int x) {
        if(tag[x]) {
            if(ls) push_reverse(ls);
            if(rs) push_reverse(rs);
            tag[x] = 0;
        }
        if (tree[x].add_tag) {
            if(ls) push_add(ls, tree[x].add_tag);
            if(rs) push_add(rs, tree[x].add_tag);
            tree[x].add_tag = 0;
        }
    } 

    inline void push_up(int x) {
        tree[x].id1 = tree[rs].id1;
        tree[x].id2 = tree[rs].id2;
        if(!tree[x].id1) {
            if(tree[x].in != 1) tree[x].id1 = x;
            else tree[x].id1 = tree[ls].id1;
        }
        if(!tree[x].id2) {
            if(tree[x].in != 2) tree[x].id2 = x;
            else tree[x].id2 = tree[ls].id2;
        }
    }

    #define get(x) (ch[f[x]][1] == x)                        
    #define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

    void rotate(int x) {
        int y = f[x], z = f[y], k = get(x);
        if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
        ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
        ch[x][!k] = y, f[y] = x, f[x] = z;
        push_up(y); push_up(x);
    }

    void update(int x) {
        if(!isRoot(x)) update(f[x]);
        push_down(x);
    }

    void splay(int x) {
        update(x);
        for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]) {
            if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);
        }
        push_up(x);
    }

    int access(int x) {
        int p;
        for(p = 0; x; x = f[p = x]) splay(x), rs = p, push_up(x);
        return p;
    }

    void makeRoot(int x) { access(x), splay(x), push_reverse(x); }

    int findRoot(int x) {
        access(x), splay(x);
        while(ch[x][0]) push_down(x), x = ch[x][0];
        splay(x);
        return x;
    }

    void split(int x, int y) {
        makeRoot(x);
        access(y), splay(y);
    }

    void link(int x, int y) {
        makeRoot(x);
        if(findRoot(y) != x) f[x] = y;
    }

    void cut(int x, int y) {
        makeRoot(x);
        if(findRoot(y) == x && f[y] == x && !ch[y][0]) {
            f[y] = ch[x][1] = 0;
            push_up(x);
        }
    }
}

using LCT::tree;

vector<int> g[N];

void dfs(int u) {
    for(auto v : g[u]) {
        dfs(v);
        tree[u].in += tree[v].out;
    }
    if(u <= n) tree[u].activate();
    // cout << "The output of node " << u << " is " << tree[u].out << endl;
}

inline void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x1, x2, x3; cin >> x1 >> x2 >> x3;
        g[i].emplace_back(x1), LCT::f[x1] = i;
        g[i].emplace_back(x2), LCT::f[x2] = i;
        g[i].emplace_back(x3), LCT::f[x3] = i;
    }
    for(int i = n + 1; i <= 3 * n + 1; i++) cin >> tree[i].out;
    dfs(1);
    int q, ans = tree[1].out; cin >> q;
    while(q--) {
        int x; cin >> x;
        int xfa = LCT::f[x];
        // cout << "Query of change : input x = " << x << ", father of x is " << xfa << endl;  
        int add_val = (tree[x].out == 1) ? -1 : 1;
        LCT::access(xfa), LCT::splay(xfa);
        int split_node = (tree[x].out == 1) ? tree[xfa].id2 : tree[xfa].id1;
        // cout << "Deepest node of found : " << split_node << endl;
        // cout << "Add_val = " << add_val << endl; 
        if(split_node) {
            LCT::splay(split_node);
            LCT::push_add(LCT::ch[split_node][1], add_val);
            // cout << "Tree[" << split_node << "].in origin value is " << tree[split_node].in << endl;
            tree[split_node].in += add_val;
            tree[split_node].activate();
            LCT::push_up(LCT::ch[split_node][1]);
            // cout << "Tree[" << split_node << "].in has been changed to " << tree[split_node].in << endl;
            // ans = tree[1].out;
        } else {
			LCT::push_add(xfa, add_val);
			LCT::push_up(xfa);
			ans ^= 1;
        }
        tree[x].out ^= 1;
        cout << ans << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173