day5下午——树上数据结构

正睿青岛

并查集按秩合并。

#

每次拿出最小的边，那么边两边的子树，都会加上另一边的siz*len。维护合并的结构，加一条边的时候，新建一个点分别连向合并的两个点，边权分别是加上的标记，最后dfs一遍即可。
并查集维护。

k级祖先

长链剖分。
每个点往上处理出跳$1,2,3...\sqrt n$步
再处理出每个点往上条$1\sqrt n 2\sqrt n ... \sqrt n \sqrt n$步

还可以处理出$1,2,3...n^{1/3}$ 步
再处理出每个点往上条$n^{1/3},2n^{1/3},3n^{1/3}...$

#

询问u到v的子树内的一个点，的最长/短路径。
dfs一下，求出1到每个点的距离。加入到线段树中，再dfs一下，每进入一个点，（经过一条边），那么就是一段区间增加L，另一段区间-L。当到达一个点后，线段树里表示的是到其他所有点的距离。直接查询一段区间。

在线：可持久化线段树。标记永久化。

在线，对每个点建可持久化线段树。

#

对于第一棵树的一个点u，它会对第一课树的终点再L[u]~R[u]的区间有贡献，然后对第二棵树的同样是一段区间有贡献。

括号序列

线段树维护两个点的路径。
splay维护。
大森林。
树上莫队。

子树众数

启发式合并。

子树的小商品

每个点可能有一些小商品，然后每个点只能从子树里买商品，每个点只卖一个，每个商品只能被卖一次。

每个点只能从子树里选，每个点选大的越好。于是从子树里合并所有没有买的商品，选一个最大的。
可并堆。

树上LIS

dp[i][j]子树i，选的点大于等于j

tips：边权非负，直径可以合并。
tips：空间往大了开，不够了，重构。

删边求直径

删除k条边，询问直径。
类似删除k条边，询问最大值。

删除一条边，就是dfs序上删除一段区间。剩下很多区间，求出所有区间的直径，直径合并。可以用栈维护，哪段区间属于哪里。
可以st表合并。
hihocoder 挑战赛23 C。

带点权，仍然是对的！