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

[P4577 [FJOI2018]领导集团问题](https://www.luogu.com.cn/problem/P4577) 这道题的题面不太清楚，我简述一下题意。 在一棵有根树上，寻找一个最大（元素最多）的节点子集 $S$，使得 $\forall x,y \in S$，如果 $x$ 是 $y$ 的祖先，那么 $w_x\le w_y$。 如果这棵树是一条链，且根是链的一端，那么这个问题就是我们熟悉的最长不上升子序列（假设序列从叶子延伸到根），可以 $\mathrm{O}(n\log n)$ 解决：设 $f[i]$ 是当前长度为 $i$ 的不上升子序列的末尾元素的最大值，那么 $f$ 在任何时刻都