这年头,啥都能上树。

回顾 LIS 问题

给出序列,求它的一个子序列,使得

这个问题有一个经典做法。维护一个序列表示长度为的 IS 的最小的末尾权值。每次在上 lower_bound 来更新。如果没有它的就在的末位加入新的元素。那么 LIS 的长度就是

如果要求的是 LNDS(longest non-descending subsequence),那么把 lower_bound 改成 upper_bound 即可。

树上 LIS

给出一棵点带权有根树,点权为。要求从中选择一个点集,使得中任意一对祖孙关系的点的祖先)都有

两棵子树的树上 LIS 是互不影响的!因此我们可以合理安排两个 LIS 的顺序使得两者的 LIS 是他们长度的和。换言之两个的数组可以直接归并。合并的时候使用启发式合并即可,multiset 维护 LIS 对应的数组。合并完子树要加入当前结点,也是 lower_bound。

时间复杂度

树上 LNDS 则是 upper_bound。

例题和代码可以看 这里