Sweetlemon 的博客

Sweetlemon 的博客

“树上 LIS”——[FJOI2018]领导集团问题

posted on 2020-07-20 09:50:05 | under 半题解 |

P4577 [FJOI2018]领导集团问题

这道题的题面不太清楚,我简述一下题意。

在一棵有根树上,寻找一个最大(元素最多)的节点子集 $S$,使得 $\forall x,y \in S$,如果 $x$ 是 $y$ 的祖先,那么 $w_x\le w_y$。

如果这棵树是一条链,且根是链的一端,那么这个问题就是我们熟悉的最长不上升子序列(假设序列从叶子延伸到根),可以 $\mathrm{O}(n\log n)$ 解决:设 $f[i]$ 是当前长度为 $i$ 的不上升子序列的末尾元素的最大值,那么 $f$ 在任何时刻都