\[\texttt{Description} \]
SP2666 QTREE4 - Query on a tree IV
\[\texttt{Solution} \]看到了动态修改的操作，所以可以考虑动态 \(\text{DP}\)。
如果没有学过动态 \(\text{DP}\)，建议左转模板区 \(\to\) P4719 【模板】"动态 DP"&动态树分治。
设 \(f_{u, 0}\) 表示以 \(u\) 为根的子树内最远的白色节点之间的距离。
设 \(f_{u, 1}\) 表示以 \(u\) 为根的子树内到 \(u\) 节点最远的白色节点的距离。
则有：
\[f_{u, 0} = \begin{cases} \max_{i \in son_u, j \in son_u, i \neq j} \{f_{i, 0}, f_{i, 1} + f_{j, 1} + 2, f_{i, 1} + 1, 0\}\ (x \small\text{为白色节点}) \\ \max_{i \in son_u, j \in son_u, i \neq j} \{ f_{i, 0}, f_{i, 1} + f_{j, 1} + 2 \}\ (x \small\text{为黑色节点}) \end{cases} \]\[f_{u, 1} = \begin{cases} \max_{v \in son_u} \{f_{v, 1} + 1, 0 \}\ (x \small\text{为白色节点}) \\ \max_{v \in son_u} \{f_{v, 1} + 1\}\ (x \small\text{为黑色节点}) \end{cases} \]根据动态 \(\text{DP}\) 的套路，我们可以进行将转移方程放到树链剖分上，改成矩阵的形式，然后用线段树维护就可以了。
设 \(g_{u, 0/1}\) 表示只考虑 \(u\) 节点的所有轻儿子得到的答案。
即：
\[g_{u, 0} = \begin{cases} \max_{i \in son_u, j \in son_u, i, j \neq hson_u, i \neq j} \{f_{i, 0}, f_{i, 1} + f_{j, 1} + 2, f_{i, 1} + 1, 0\}\ (x \small\text{为白色节点}) \\ \max_{i \in son_u, j \in son_u, i, j \neq hson_u, i \neq j} \{ f_{i, 0}, f_{i, 1} + f_{j, 1} + 2 \}\ (x \small\text{为黑色节点}) \end{cases} \]\[g_{u, 1} = \begin{cases} \max_{v \in son_u, v \neq hson_u} \{f_{v, 1} + 1, 0 \}\ (x \small\text{为白色节点}) \\ \max_{v \in son_u, v \neq hson_u} \{f_{v, 1} + 1\}\ (x \small\text{为黑色节点}) \end{cases} \]所以转移方程可以简化为：
\[f_{u, 0} = \max\{g_{u, 0}, f_{hson_u, 0}, f_{hson_u, 1} + 1, g_{u, 1} + f_{hson_{u}, 1} + 1\} \]\[f_{u, 1} = \max\{g_{u, 1}, f_{hson_u, 1} + 1\} \]我们新定义矩阵，设有矩阵 \(C = A \times B\)，则：
\[C_{i, j} = \max\limits_{k = 1}^{k \leq m} \{ A_{i, k} + B_{k, j} \} \]我们设一个答案矩阵为 \(\begin{vmatrix} f_{u, 0} \\ f_{u, 1} \\ 0 \end{vmatrix}\)，则有：
\(\begin{vmatrix} f_{u, 0} \\ f_{u, 1} \\ 0 \end{vmatrix} = \begin{vmatrix} 0 & \begin{cases} \max\{g_{u, 1}, 0\} + 1\ (x \small\text{为白色节点}) \\ g_{u, 1} + 1\ (x \small\text{为黑色节点}) \end{cases} & g_{u, 0} \\ -\infty & 1 & \begin{cases} \max \{ g_{u, 1}, 0 \}\ (x \small\text{为白色节点}) \\ g_{u, 1}\ (x \small\text{为黑色节点}) \end{cases} \\ -\infty & -\infty & 0 \end{vmatrix} \times \begin{vmatrix} f_{hson_u, 0} \\ f_{hson_u, 1} \\ 0 \end{vmatrix}\)
接下来考虑在树链剖分上如何转移，具体一点，就是在一条重链上如何转移。
如图所示，假设 \(1 \to 2 \to 3\) 为一条重链，\(4 \to 5\) 为另一条重链。
我们假设要翻转 \(5\) 号节点的颜色，我们可以考虑如何快速计算出 \(g_{5, 0/1}\) 的值，从而改变 \(5\) 号节点的转移矩阵。
根据 \(g\) 数组的转移方程，我们可以考虑在每一个节点 \(u\) 设 \(2\) 个 \(\text{multiset}\) 分别维护 \(\forall v \in son_u, v \neq hson_u\) 的 \(f_{v, 0}\) 以及 \(f_{v, 1}\)。
这样我们就可以在 \(\mathcal{O(\log n)}\) 的时间复杂度内得出 \(f_{v, 0}\) 的最大值以及 \(f_{v, 1}\) 的最大值和次大值。
接着考虑其到根节点路径上的节点。
由于 \(5\) 号节点是 \(4\) 号节点的重儿子，所以并不会对 \(4\) 号节点的转移矩阵产生影响，一直到整条重链的顶端的父亲节点，也就是 \(2\) 号节点，\(4\) 号节点就成为了 \(2\) 号节点的轻儿子，所以可以先根据线段树维护矩阵乘法将 \(f_{4, 0/1}\) 计算出来，并且然后在 \(2\) 号节点的 \(2\) 个 \(\text{multiset}\) 中删去 \(f_{4, 0/1}\)，接着修改 \(5\) 号节点的矩阵，并再次利用线段树求出修改后的 \(f_{4, 0/1}\)，在 \(2\) 号节点的 \(2\) 个 \(\text{multiset}\) 中加入新的 \(f_{4, 0/1}\)，然后计算出 \(g_{2, 0/1}\) 并且修改 \(2\) 号节点的转移矩阵，在考虑 \(2\) 号节点到根节点路径上的节点时只需要以此类推即可。
时间复杂度 \(\mathcal{O(n \log^2 n)}\)，带了一个 \(3 ^ 3 = 27\) 的常数。
其实可以用全局平衡二叉树做到时间复杂度 \(\mathcal{O(n \log n)}\)，由于本蒟蒻不会这种高科技 （菜是原罪），所以这里不再赘述。