「Trick」树上 LIS

这年头，啥都能上树。

回顾最长上升子序列问题

最长上升子序列问题（longest increasing subsequence, LIS）指

给出序列$a_1, \ldots, a_n$，求它的一个最长的子序列$b$，使得$b_i<b_{i+1}$。

这个问题有一个经典$O(n\log_2n)$做法。维护一个序列$d_i$表示长度为$i$的上升子序列的最小的末尾权值。每次在$d_i$上二分查找（lower_bound）来更新。如果没有$\ge$它的就在$d$的末位加入新的元素。最终 LIS 的长度就是$|d|$。

如果要求的是最长不下降子序列（longest non-descending subsequence，LNDS），那么把 lower_bound 改成 upper_bound 即可。

树上 LIS

给出一棵点带权有根树，点权为$c_u$。要求从中选择一个点集$S$，使得$S$中任意一对祖孙关系的点$u,v$（$u$是$v$的祖先）都有$c_u<c_v$。

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

时间复杂度$O(n\log_2^2n)$。

树上 LNDS 则是 upper_bound。

例题和代码可以看 这里。