杂题思路笔记

本贴用来记录口糊出来的杂题的思路、做法等。

没有代码，可能有错。

CF490F Treeland Tour

题目链接。

DFS + 线段树合并。

树上最长上升子序列在一个以 $u$ 为根的子树内可以看作以 $f\_{i}-1$ 为结尾的 LIS + 1（$u$ 节点）+ 以 $f\_{i}+1$ 为结尾的 LDS。

至于子树内的 LIS 之前肯定更新过了。

具体的，进行 DFS，从孩子向父亲更新。

对于每个节点，开一棵权值线段树，第 $i$ 个叶子结点存以数值 $i$ 为结尾的 LIS。

DFS 向上回溯时，从以 $u$ 的儿子 $v$ 为根的子树中找出一条最长的 LIS，更新答案，再将 $v$ 的权值线段树合并到 $u$ 上。

合并的时候再考虑一下从已更新的其他儿子的子树中找出的 LIS 或 LDS 与 $v$ 的子树中 LDS 或 LIS 加上 $u$ 形成的 LIS 对答案的贡献。

处理完 $u$ 的子节点后回溯之前将 $f_{u}$ 加到 $u$ 的权值线段树里去。

P3224 [HNOI2012]永无乡

题目链接。

思路非常简单。

用并查集维护连通块内有哪些岛，再线段树合并到连通块内的根的权值线段树上。