HDU6065证明

order

$\forall[l,r],\exists i,j\in [l,r]\;s.t. \;lca(a_l,a_{l+1},\cdots,a_r)=lca(a_i,a_j)$

问题等价于：选出$k$对点（允许某几对点退化成一个点），这$k$对点确定的区间不相交，并且这$k$对点的$lca$深度之和最小。

结论：最优方案中的每一对点要么是相邻的两个点，要么是同一个点。

证明：

对于$(i,j)$，如果存在$i<k<j$ ：

如果$dep(lca(i,k))\le dep(lca(i,j))$，那么区间$[i,j]$的$lca$不能由$(i,j)$确定。

否则$dep(lca(i,k))> dep(lca(i,j))$，那么$lca(i,j)=lca(j,k)$，那么，我们选$(j,k)$为一对，让$i$找其它点和它一对（或者舍弃$i$）答案会更优。

因此，最优方案中的每一对点要么相邻，要么是同一个点。