原题大战.
$dna$
学了回文自动机再来更.
$color$
其实应该算是原题的弱化版.
记 $dist(x)$ 表示根节点到 $x$ 的距离, $dis(x,y)$ 表示 $x,y$ 之间的距离.
$$
\begin{aligned}
ans&=\sum_{y=1}^{k} dis(x,y) \\
&=\sum_{y=1}^k dist(x)+dist(y)-2\cdot dist(LCA_{x,y}) \\
&=dist(x)\cdot k+\sum_{y=1}^{k} dist(y)-2\cdot\sum_{y=1}^k dist(LCA_{x,y})
\end{aligned}
$$
前面两项都容易维护,考虑如何计算最后一项的贡献.
$dist(LCA_{x,y})$ 其实就是 $x$ 到根的路径与 $y$ 到根的路径交集部分的长度.
每新染黑一个 $y$ ,就将 $y$ 到根节点上的每条边标记 $+1$ .
询问时,最后那一项就是 $x$ 到根节点路径上每条边的 标记次数 $\times$ 边长.
可以用树链剖分 + 线段树来维护,时间复杂度 $O(n\log^2 n)$ .
$land$
题目中已经告诉我们怎么判断一个格子是否在多边形内部,这个判断条件只跟穿过次数奇偶性有关.
可以利用它进行状压 $dp$.
给每个格子选一条射线,在转移的过程中更新有宝藏和陷阱的格子那条射线穿过边的奇偶性状态.
$f(i,j,S)$ 表示当前在格子 $(i,j)$ ,宝藏和陷阱的射线奇偶性状态为 $S$ 时,多边形最小周长.
转移时直接 $bfs$ ,最后枚举哪些宝藏被圈了起来,统计答案.