QTREE7 - Query on a tree VII

· · 题解

\texttt{Qtree} 系列之树剖全解

还是利用 QTree4 的思想

线段树合并：当前节点 p ,表示区间为 [L,R]

设 lmx_{p} 表示 L 所在同色连通块内的最大权值

设 rmn_{p} 表示 R 所在同色连通块内的最大权值

光这样显然是合并不了的，考虑合并需要什么

对于当前节点 p[L,R]，左右儿子分别为 ls[L,mid]，rs[mid + 1, R]

显然 lmx_{ls} 可以贡献给 lmx_p，但 lmx_{rs} 呢？

如果左儿子全是一个颜色，并且与右儿子最左边的颜色相同，那么是不是 lmx_{rs} 也可以贡献给 lmx_p？

所以设 lsiz_p 表示左端点所在同色连通块包含区间内的点数（即 L 在重链上的同色连通块的大小），rsiz_p 同理

那么转移就出来了：

lmx_p = \max(lmx_{ls} , lmx_{rs}[lsiz_{ls} = mid - l + 1][col_{mid} = col_{mid +1}]) rmx_p = \max(rmx_{rs} , rmx_{ls}[rsiz_{rs} = r - mid][col_{mid} = col_{mid+}]) lsiz_p = lsiz_{ls} + lsiz_{rs}[lsiz_{ls} = mid - l + 1][col_{mid} = col_{mid +1}] rsiz_p = rsiz_{rs} + rsiz_{ls}[rsiz_{rs} = r - mid][col_{mid} = col_{mid +1}]

边界情况：设 v 为 u 的轻儿子

lmx_u = rmx_u = \max\limits_v \{lmx_{rt_v}[col_u = col_v], w_u\} lsiz_u = rsiz_u = 1

询问：

只需跳到最浅的，同一同色连通块内的祖先，再查，该祖先到其所在链链底这个区间， lmx 即为答案，但要注意特判跳到根的情况，以及跳时颜色是否相同，细节看代码，注意有负权值！

修改：

先删除原来的贡献，加入新的贡献，这个只需每个点每个颜色用一个 multiset 维护，记录该颜色连通块内的最大权值即可

然后一边跳重链一边改，同时记录上一个节点（从哪里跳来），和之前的贡献，以便删除贡献和添加贡献，细节在于改颜色时上一个点是否就是修改的点，如果是，在删贡献是要在反色 multiset 里面删（它原来的贡献是存在那里面的）

最开始相的是用建虚点改二叉树，虚点设为通用颜色，但后面对拍才发现根本不行，因为虚点会将两种颜色的最大权值混在以前，还是只有老老实实写 multiset

也是调了好久，拍了一下午

好在树剖依旧稳定输出，拿下最优解第四

code