LuoguLOJ分析看题解发现一个神仙做法。发现我们要求的是一个类似于 LIS 的东西，我们随便取个名字叫树上 LIS。对于每个节点维护一个 multiset ，满足它的第 $i$ 个元素表示子树中选 $i$ 个点的所有树上 LIS 中最小的 $w$ 的最大值。可以发现每个节点的答案就是它的 multiset 的大小。考虑怎么更新。首先把所有子节点的 multiset 启发式合并上来，然后再...
LuoguBZOJ分析先考虑一条链的情况怎么做。显然 $1$ 最多会有两条支链，那么两条支链排序后对应相加即可。正确性显然。考虑把这个东西扩展到树上。每个节点维护一个堆，然后向上启发式合并即可。时间复杂度为 $O(n\log n)$ 。代码// ================================= // author: M_sea // website: http://...