题解【CF1149C Tree Generator™】

UperFicial · 2022-10-05 16:21:30 · 题解

CF1149C Tree Generator™

不一定更好的阅读体验。

牛逼题 & ZROI Day3 数据结构选讲。

来一波详细的题解。

当时和 \texttt{ys}，\texttt{hy} 还有小猴子讨论了半天，一直认为是最大子段和很激动直接就在群里说了，结果被喷了，然后一波周折群友觉得这是十分正确的，然后一波周折又被喷了（

考虑把 ( 看成深度 +1，) 看成深度 -1，那么就可以把括号序列看成一个 +1 和 -1 的序列。

考虑一条路径的长度如何算，对于一段 u\to \operatorname{lca}(u,v)\to v 的路径，在括号序列上肯定会被表示成形如 )...)(...( 的一段，路径长度为 ( 括号数量 + ) 括号数量。

但是，如果路径上还会有一个子树，比如形如 )..()..)(..(，() 是需要忽略不计的。

由此我们得到结论：括号序列上任何一个子区间，去掉所有匹配的括号后，得到的括号序列一定是树上一条链。如果用权值表示法来表示，你会发现其实匹配的括号根本不用管，因为一个 (+1) 和一个 (-1) 都消掉了，如果我们称 )( 为分界点，( 右边的部分为右区间，) 左边的部分为左区间，那么这条路径的长度为，右区间的权值和 + 左区间权值和的相反数，因为左区间的 ) 我们表示成了 -1，现在需要算成 1 的长度。

对此，我们又得到一个结论：对于所有子区间，找到一个分界点，右区间权值和 - 左区间权值和的最大值，为这个子区间的路径长度最大值。

那么显然，树的直径是对于所有子区间，找到一个分界点后的权值最大值。

交换字符可以看成 \Theta(1) 的修改，那么很自然地想到用线段树来维护这个东西，且类似于最大子段和。

维护区间答案 \text{ans}，后缀最大值 \text{sm}，后缀最小值 \text{sn}，前缀最大值 \text{pm}，前缀最小值 \text{pn}。

但这样是不足以转移的，比如左区间是 ))) 右区间是 ))(，你完全可以一起拼一块儿。

所以我们还要维护一下，紧靠左端点的答案最大值 \text{lm}，紧靠右端点答案最大值 \text{rm}，紧靠左右端点的答案最大值 \text{lrm}，以及区间和 \text{sum}。

考虑 \texttt{pushup} 的过程，设 u 的左右儿子分别为 u_0 和 u_1。

• 首先很显然的 \text{ans}_u\leftarrow \max(\text{ans}_{u_0},\text{ans}_{u_1})。

• 还可以是左区间已经是包含右端点的完整答案了，右区间在拼上一个 (..( 的最长前缀，\text{ans}_u\leftarrow \text{rm}_{u_0}+\text{pm}_{u_1}。

• 当然完整答案在右区间的情况也同理，\text{ans}_u\leftarrow \text{lm}_{u_1}-\text{sn}_{u_0}。

前缀最小值 / 最大值都可以通过区间和来转移，考虑 \text{lm} 的转移，首先可以直接继承 \text{lm}_{u_0}，还让左区间紧靠左右端点的答案再拼上右端点的 (..(，即 \text{lrm}_{u_0}+\text{pm}_{u_1}，还可以是右区间选择一个紧靠左端点的答案段 )..)(..(，然后左区间全部选择，只不过这里需要注意取反，\text{lm}_{u_1}-\text{sum}_{u_0}。\text{rm} 是同理的。