【LG-P4332 [SHOI2014]】三叉神经树 题解

pldzy

2022-04-08 21:37:48

Personal

题面挺有意思(恶心)的。

传送门:P4332 [SHOI2014]三叉神经树

LCT

Solution

1

对于每一个非叶子节点 i,有 val_i,表示其输出为 1 的儿子的总数。

所以对于每一个 val_i,\ i \in [1,n] ,其取值范围是 0~3。所以我们发现这个非叶子节点 i 最后输出的结果就是 \left\lfloor\dfrac{val_i}{2}\right\rfloor

而对于叶子节点 j(即编号范围为 (n, 3 *n +1]),

假设它的输出是 xx 为 0 或 1),为了保证其输出结果是 \left\lfloor\dfrac{val_j}{2}\right\rfloor,我们使 val_j \gets x *2

*所以对于每个 $val_j,\ j \in (n, 3 n + 1]$,其取值只有 0 或 2 两种可能性**。

对于 val 的计算,我们可以在输入后拓扑排序得到。

2

我们都会模拟暴力过程——先改叶子节点(先默认为 0 改为 1),如果它的父亲此时权值为 1 的儿子数量从原来小于 0 的变成大于 0 的,那么父亲的权值也要改。以此类推,直到有一个节点输出状态没有变化,那么它的所有祖先肯定不会变。

通过模拟我们发现,每次修改的一定是一段自底向上的连续区间!

接着也就不难想到,只有当点权为 1 时,才能通过修改点权变成 2,使输出由 0 变成 1,从而继续引发祖先的变化。那么我们需要知道的就是,对于每一个叶子节点,它自底向上的连续一段点权为 1 的部分。

再讨论叶子节点 1 改 0 的情况,同理也可以发现我们还要维护自底向上的连续一段点权为 2 的部分。

”——摘自洛谷P4332 [SHOI2014]三叉神经树题解 by FlashHu

大佬已经说得很清楚了,要维护区间,所以使用 LCT,同时间维护两个数组 n1n2

每次我们先打通(即 $access$)到叶子节点 $x$ 的父亲节点 $f_x$(因为至少是从 $f_x$ 开始造成影响),再 $splay(f[x])$,(假设 $x$ 是由 0 变为 1)然后 $splay(n1[f[x]])$。 这样一来,会发生改变(即 $val$ 在 1 和 2 之间变换)的部分就是 $n1[f[x]]$ 的右子树了。所以最后我们对该右子树进行区间修改,对 $n1[f[x]]$ 进行单点修改。 ### 3 如何区间修改。 发现那些需要进行修改的区间,内部所有的节点的权值要么都是 1,否则就都是 2。而我们对它们的操作无非就是: - 点权为 2,减 1; - 点权为 1,加 1。 所以,我们实际上只用对这个区间做一个类似“翻转”的操作(可以理解为在权值方面的翻转)即可。 ## Code 吐槽:FlashHu 大佬的代码太难理解了!!! ```cpp #include<bits/stdc++.h> using namespace std; #define rep(i, a, b) for(register int i = a; i <= b; ++i) #define ls c[x][0] #define rs c[x][1] const int maxn = 5e5 + 5, maxm = 15e5 + 5; int n, qu; int f[maxm], val[maxm]; int c[maxn][2], tag[maxn], n1[maxn], n2[maxn]; int d[maxn]; int tp, nwrt; queue <int> q; inline int rd() { int s = 0, x = 1; char ch = getchar(); while(ch < '0' or ch > '9') {if(ch == '-') x = -1; ch = getchar();} while(ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return x * s; } inline bool nrt(int p) { int x = f[p]; return ls == p or rs == p; } inline void up(int x)//为了尽可能深,所以先右子树再当前节点最后左子树 { int &p = n1[x], &q = n2[x]; p = n1[rs]; if(!p) p = x * (val[x] != 1); if(!p) p = n1[ls]; q = n2[rs]; if(!q) q = x * (val[x] != 2); if(!q) q = n2[ls]; } inline void dw(int x, int k) { int &v = val[x]; if(v == 2) v = 1; else v = 2; swap(n1[x], n2[x])/*容易发现更改权值的时候n1n2也跟着翻转了*/, tag[x] += k; } inline void all(int x) { int &tm = tag[x]; if(nrt(x)) all(f[x]); if(tm) dw(ls, tm), dw(rs, tm), tm = 0; } inline void rotate(int x) { int y = f[x], z = f[y], k = (c[y][1] == x), w = c[x][!k]; if(nrt(y)) c[z][c[z][1] == y] = x; f[x] = z, c[y][k] = w; if(w) f[w] = y; c[x][!k] = y, f[y] = x; up(y); } inline void splay(int x) { all(x); while(nrt(x)) { int y = f[x], z = f[y]; if(nrt(y)) rotate((c[z][1] == y) ^ (c[y][1] == x) ? x : y); rotate(x); } up(x); } inline void access(int x) { for(int lst = 0; x; x = f[lst = x]) splay(x), rs = lst, up(x); } int main() { n = rd(); rep(i, 1, n) f[rd()] = f[rd()] = f[rd()] = i, d[i] = 3/*入度*/; rep(i, n + 1, 3 * n + 1)//叶子节点 q.push(i), val[i] = rd() << 1; while(!q.empty())//拓扑排序 { int u = q.front(); q.pop(); if(u <= n) up(u); val[f[u]] += (val[u] >> 1), d[f[u]] -= 1; if(!d[f[u]]) q.push(f[u]); } nwrt = val[1] >> 1, qu = rd(); while(qu--) { int x = rd(), &v = val[x]/*该叶子节点原本输出的值*/; if(!v) v = 2/*更改输出值*/, tp = 1/*标记输出值是从 0 变成 1*/; else v = 0, tp = -1; access(x = f[x]), splay(x); if((tp > 0 ? n1 : n2)[x]) { splay(x = (tp > 0 ? n1 : n2)[x]); dw(rs, tp), up(rs);//区间修改 val[x] += tp, up(x);//单点修改 } else dw(x, tp), up(x), nwrt ^= 1; printf("%d\n", nwrt/*优化,省时间*/); } return 0; } ``` --------------------- ——$End$——