树上 LIS 的套路之一
因为是从 yyb 博客上抓的题,所以知道可以用线段树做。大概想了想,初步的想法就是用线段树来维护不同高度(?)的最长子序列长度。其实这样是可以的,输入高度时就先塞到每个点的动态开点线段树里,然后就可以把儿子的进行合并。合并儿子的时候,维护至少为 \(x\) 时能得到的最长子序列长度,所以我们可以用差分的方式来做一做(当然也可以做标记永久化的区间加):从 \(w_u\) 的位置开始加上一个一,然后把上一次的 \(1\) 给删掉。
因为是从 yyb 博客上抓的题,所以知道可以用线段树做。大概想了想,初步的想法就是用线段树来维护不同高度(?)的最长子序列长度。其实这样是可以的,输入高度时就先塞到每个点的动态开点线段树里,然后就可以把儿子的进行合并。合并儿子的时候,维护至少为 \(x\) 时能得到的最长子序列长度,所以我们可以用差分的方式来做一做(当然也可以做标记永久化的区间加):从 \(w_u\) 的位置开始加上一个一,然后把上一次的 \(1\) 给删掉。