Luogu 3647 - [APIO2014]连珠线

较为繁琐的树形 $\mbox{DP}$ 。

不难发现除了根节点以外,不可能构成横向的蓝色三元组,一定是纵向的蓝色三元组。

令 $f_{i, 0/1}$ 表示以 $i$ 为根,其是否是三元组的中间点。三元组包括三个点,两条边,上下两点是可以和别的三元组重复的,关键是要记录两条边。

有方程:

即 $b_i$ 为上式的次大值。

考虑换根:

1
2