CF1814E Chain Chips
好久没写这种题了~~
不带修时，为了让总距离和最短，考虑让相邻的车互换位置，但如果单纯这样有可能剩下一辆车，那就让相邻的三辆车换一下。发现当车的个数 \(x \ge 4\) 时，都可以拆成 \(2\) 辆或 \(3\) 辆车。对应到边就是只能选相邻的一条边或两条边。设 \(dp_i\) 表示第 \(i\) 条边必选且满足条件的答案，那么：
\[dp_i = \min(dp_{i-1}, dp_{i-2}) + a_i
\]
利用加法对取 \(\text{min}\) 操作的分配律，转化为广义矩乘递推：
\[\begin{bmatrix}
dp_{i-2} & dp_{i-1}
\end{bmatrix}
\begin{bmatrix}
\infty & a_i \\
0 & a_i
\end{bmatrix}
=
\begin{bmatrix}
dp_{i-1} & dp_i
\end{bmatrix}\]
用线段树维护支持修改。
CF1774E Two Chess Pieces
考虑每个棋子必须经过哪些点：
- 子树里有己方标记点的点
- 与子树中对方最深标记点距离大于 \(d\) 的点
除根结点外每个需经节点贡献为 \(2\)，一遍 \(\text{dfs}\) 解决。