树上算法
- 轻重链技术
- dsu on tree
- 边分治
- 边分树
- 点分治和动态点分治
- 树上最远点对
- 树上中点（边）
- 最小子树统计
- 长链剖分
- 双树问题
- 一类树上分割问题
- 树上路径统计问题
- LCA算法及应用
- 子树划分问题
- 一类树划分问题
- 树上匹配问题
- 树上监视问题
- 度数转树问题
- 树上距离和
- 树上路径中最大权边
- 括号序列/dfs序
轻重链技术
轻重链技术，是指我们将树上的边分成两类，轻链和重链。一个结点的大小最大的子树，称为这个结点的重孩子（一个结点最多只有一个重孩子），与重孩子相连的边叫做轻边。
考虑从任意一个顶点向根结点走，没经过一条轻边，则子树大小至少翻倍，因此可以直接推出任意一个顶点到根结点路径上最多有$O(\log_2n)$条轻边。
又了上面的结论我们就可以实现很多算法。比如dsu on tree、轻重链剖分。
题目1：给定一颗前缀树，每条边上都标记一个小写字母。现在希望选择某个$p$，并将前缀树中所有长度大于等于$p$的字符串都删除掉第$p$个字符。之后重新构建前缀树，要求新的前缀树包含尽可能少的顶点。其中$n\leq 3\cdot 10^5$
考虑删除第$p$层的所有顶点带来的影响，我们需要合并删除的顶点下的子树。
具体实现就是我们进行DFS，对每个结点计算删除其所有孩子后可以得来的优化。我们将所有其它剩余的子树合并到重孩子的重孩子中去。可以发现每个结点每次合并到其余子树去（贡献1），对应孩子到父亲的路径中两条连续边其中至少一条边为轻边，很显然每个孩子最多产生贡献$O(\log_2n)$。
总的时间复杂度为$O(26n\log_2n)$，其中$26$来自于字符集。
一道CF题目。
dsu on tree
树上DP有很多种形式，下面给出一个树上DP的题目：
n个结点，每个结点有一个颜色，要求我们计算每个结点作为根的子树中不同的颜色数目。
这个问题，你可以通过哈希表以及启发合并来实现，这样的时间复杂度就为$O(n\log_2{n})$。
当然由于哈希表的常数和消耗的空间会略大，你可以使用莫队算法，这样的时间复杂度为$O(n\sqrt{n})$。
还有一种就是使用一种树上启发合并的方式，内容来自于这篇博客Sack (dsu on tree)。Dsu on tree算法适用于有根树的所有子树的DP。下面说一下流程：
首先我们要对有根树进行轻重链剖分。
之后我们对树进行深度优先搜索，计算DP值。计算DP值分成三步，对由轻链连接的子树递归调用当前过程，但是要清除它们带来的影响（我们会维护一个全局的数组，记录子树的状态，在这个问题中就是一个布尔数组，记录颜色是否出现，这里消除影响的意思是将数组恢复到对这些子树调用递归过程之前的状态）。之后我们对重链边连接的子树进行递归调用，但是保留它们的状态，并用在当前结点的状态计算上。之后分别对轻链连接的子树调用一次递归过程，但是这个过程既不是为了计算子树的DP，也不要求清除状态，但是要把原来的状态附加到现有的状态上。
因此我们可以将DFS分成两种，第一种我们称为动态规划流程，其目的是为了利用子树的状态计算当前结点的DP值，我们称为计算过程；第二种是不计算自己的DP值，而只是贡献自己的状态信息，我们称为贡献流程。
而我们会为每个结点调用一次计算流程，会为每条轻链连接的子树调用一次贡献流程。当然你可能会问，为什么不在计算流程中把计算结果保存下来呢，这样只需要合并一下，而不需要使用慢的多的贡献流程。原因是这样的，味为每个结点都保存状态，考虑所有的结点仅于根结点有一条连接的边，那么我们在计算跟结点的状态的同时，还需要保存(n-1)份状态信息，而每份状态信息的大小都是$|C|$，C是可能的颜色的集合。当然你会说我们可以使用哈希表来节省内存，但是使用哈希表的话性能会大幅度恶化，而且同样也会占用大量的空间，这样对于时间和空间限制比较严格的情况下是很难通过的。
下面聊聊时间复杂度。在我们上面的问题中，计算流程的时间复杂度为$O(n)$，而贡献流程，每个结点最多会参加与自己到根结点的路径上轻边数目相同次数的贡献流程（在任意一颗大小为$n$的树中，每条一个端点为根结点的路径最多有$\log_2{n}$个轻边），而每次参加的时间复杂度为$O(1)$，共$n$个结点，因此贡献流程的总时间复杂度为$O(n\log_2{n})$。轻重链剖分的时间复杂度为$O(n)$，因此总的时间复杂度为$O(n\log_2{n})$。
边分治
边分治类似于点分治，区别在于点分治找的是重心点，而边分治找的是重心边。
树$T$的重心边是指这样一条边$e$，使得删除$e$后得到的两个连通块大小的最大值最小，我们记作$\mathrm{effect}(e)$。
由于对于菊花图，任何边得到的连通分块的大小都是$1$和$n-1$，因此边分治不能得到很好的效果。我们可以插入一些假的顶点，使得每个顶点下只挂两条边（不包括与父亲相连的边）。
现在在已知树中每个顶点的度都不超过$3$的前提下，我们证明假如$e$是树$T$的重心，且$T$的大小为$n$，那么$\mathrm{effect}(e)\leq \frac{2}{3}n$。实际上假设$e$是树$T$的重心，连接两个顶点$u$、$v$。不妨认$u$所在连通块的大小大于$\frac{2}{3}n$。考虑到$u$至多还能连接两条边，因此至少有一条边$e'$的另外一端所在连通块的大小能达到$\frac{1}{3}n$。$e'$是比$e$更好的重心。
边分治的优势在于边连接的一定是父子，因此可以将树分成两部分，包含根的记作$R$，不含根的记作$B$。而$R$中任意顶点$x$，与$B$中所有顶点的LCA是相同的，因此可以提前计算并用于后面的处理。
边分树
考虑要处理这样的问题，有两棵树T1和T2，对于某个不同顶点对u、v，定义它们的距离为：
\[dist(u,v)=dist_1(u,v)+dist_2(u,v)\]其中$dist_1$为第一颗树上的距离，$dist_2$是第二颗树上的距离。这个问题可以通过边分数来消除第一颗树上LCA带来的影响，之后为第二颗树建立虚树，可以消除第二颗树上LCA的影响，之后就成为一般的DFS统计最远顶对问题，时间复杂度是$O(n(\log_2n)^2)$。
可以用另外一种叫做边分树的技术来优化。我们为每个顶点额外维护一个二叉树，初始时只有一个顶点。在对第一个树进行边分治时，删除边重心后，会得到两个连通块，记作a、b。我们将a上的顶点二叉树深度最大的叶结点下加上一个左孩子，为b上顶点二叉树深度最大的叶结点下加上一个右孩子。完成了边分治后，每个顶点所对应的二叉树实际上都是一条弯曲的链表（长度为$O(\log_2n)$），之后我们在第二颗树上进行DP操作。对于每个顶点，当递归处理完一个子结点时，就将它的二叉树和自己的二叉树进行合并，合并的时候对于处于二叉树左右不同分支的顶点，可以统计其贡献。这样就能在$O(n\log_2n)$的时空复杂度下解决问题。
点分治和动态点分治
点分治的基本原理是找到树的重心。一个顶点称为重心，当且仅当删除它之后，得到的所有连通块大小都不超过树大小的一半。可以证明重心始终是存在的，并且一颗树的重心数目最多只有两个。
点分治的流程如下：
- 找出树的重心$C$。
- 统计经过$C$的所有路径信息。
- 删除$C$。
- 对得到的新的连通分块递归调用这个流程。
点分治的用处是统计一些满足特殊性质的路径，比如长度不超过$k$的路径数目。可以发现点分治的深度最多为$\log_2n$，且每个顶点在一层最多贡献一次，因此总的顶点贡献次数为$O(n\log_2n)$。
一般点分治是离线操作，但是如果我们根据这个流程构建点分树就可以实现在线操作，其原理类似于离线二分，将每次流程的数据保留下来，根据流程的调用关系，可以构建一颗深度不超过$\log_2n$的树。
之后对于查询操作，我们可以从顶点出发，不断向上跳。但是这里依旧有一些难点，比如说在处理重心$C$的时候以及其某个孩子$u$，如何获取不包含以$u$为根的子树的信息，这个一般只能通过差分的技术来完成，或者通过持久化技术来做。
如果在上面的过程中，我们使用的是差分技术，那么我们可以基于点分树实现动态点分治，即允许单点修改操作。具体的原理是为每个顶点$i$维护两个信息，$A_i$表示以$i$个重心的流程的统计信息，$B_i$表示该流程代表的连通块，对父流程的贡献。之后对于单点操作，我们修改$A$和$B$最多各$\log_2n$次。
题目1：给定$n$个顶点，每个顶点都有各自的点权。之后$q$个请求，请求分为两类：
- 修改某个点的点权
- 给定$u$和$k$，统计所有距离$u$不超过$k$的顶点的点权和。
提供一道题目。
动态点分治的裸题。
树上最远点对
命题1：如果树上边权非负，对于两个顶点集合A、B，设A中最远点对为$a_1,a_2$，而B中最远点对为$b_1,b_2$，那么在A、B合并后，其中最远点对一定可以从$\left\{a_1,a_2,b_1,b_2\right\}$中得到。
命题2：如果树上边权非负，并定义树上距离为路径距离加上两点的点权，对于两个顶点集合A、B，设A中最远点对为$a_1,a_2$，而B中最远点对为$b_1,b_2$，那么在A、B合并后，其中最远点对一定可以从$\left\{a_1,a_2,b_1,b_2\right\}$中得到。
命题3：如果树上边权非负，那么以任意顶点为根，从最深的顶点中选择一个顶点，这个顶点一定是某个树上直径的端点。
树上中点（边）
如果一颗树的直径为$D$。
如果$D$是偶数，那么树上一定存在一个顶点，到其它所有顶点的距离不超过$D/2$，这个顶点称为树的中点。
如果$D$是奇数，那么树上一定存在一条边，使得其它所有顶点到边的某一端的顶点的距离不超过$(D-1)/2$，这条边称为树的中边。
任意取一条树上直径，如果直径长度为偶数，那么直径中心的顶点就是树的中点，假如直径长度为奇数，那么直径中心的边就是树的中边。
如果树上有多个直径，那么树上所有直径都一定过中点（中边）。
最小子树统计
对于一株树$T=(V,E)$，对于任意$V$的子集$S$，包含$S$的顶点最少的子树的顶点数目记作$f(S)$。
要求：$\sum_{S\subset V}f(S)$
这个问题站在顶点的角度看，是很难解决的。但是如果站在边的角度看问题就很简单了，记$g(S)$表示包含$S$的顶点最少的子树中的边集。那么我们可以推出：
\[\begin{aligned} \sum_{S\subset V}f(S)&=\sum_{S\subset V}(\sum_{e\in g(S)}1+1)\\ &=\sum_{S\subset V}\sum_{e\in g(S)}1+2^{|V|}\\ &=\sum_{e\in E}\sum_{S\subset V}[e\in g(S)]+2^{|V|} \end{aligned}\]其中$[e\in g(S)]$为1，当且仅当$S$中包含从$T$中删除$e$后得到的两个子树中顶点至少一个。因此我们利用容斥，从所有可能的$V$的子集中删除仅覆盖$e$一侧顶点的集合数即可得到，记$L(x)$表示边左侧子树大小，$R(x)$表示边右侧子树大小，那么结果就是：
\[\sum_{S\subset V}[e\in g(S)]=2^{|V|}-2^{L(e)}-2^{R(e)}+2^{0}\]因此最终结果可以表示为：
\[\begin{aligned} \sum_{S\subset V}f(S)&=\sum_{e\in E}\sum_{S\subset V}[e\in g(S)]+2^{|V|}\\ &=\sum_{e\in E}(2^{|V|}-2^{L(e)}-2^{R(e)}+2^{0})+2^{|V|} \end{aligned}\]这个可以通过dfs线性统计出来。
长链剖分
长链剖分可以用于解决一些树上与高度相关的DP问题。
长链剖分类似于dsu on tree。
首先我们要处理出一颗树中的长链。记$L(x)$表示顶点$x$到以$x$为根的子树中最深的叶节点的距离。对于任意结点$x$，设$y$为$x$直接子结点中$L(y)$最大的（如果有多个最大，则仅选择其中一个），那么我们将$x$和$y$之间的边称为长边，由长边组成的路径称为长链。这样操作后，整颗树将包含若干条链，这些链没有公共顶点和公共边，并且每个结点唯一属于一条链。
性质1：由于没有公共边，所有长链的总长度不超过$n$。
性质2：顶点$x$的$k$级祖先$y$所在链的长度一定不小于$k$
证明：
如果$x$和$y$处于同一长链，很显然成立。
否则由于$x$在$y$的子树中，故$L(y)>=k$，因此可知$y$所在长链一定不小于$k$。
在线查询树上某个结点的$k$级祖先
我们可以使用倍增算法找到每个顶点的所有$2^i$祖先顶点。之后对于所有长链顶部结点$x$，为其创建两个两个大小为$L(x)-1$的数组$A$、$B$，其中$A$保存$x$上面$L$个顶点，而$B$保存$x$沿着长链向下的$L$个顶点。之后还需要预先计算$1$到$n$中每个数的二进制最高位。上面的所有过程总的时间复杂度为$O(n\log_2n)$，空间复杂度为$O(n\log_2n)$。
之后对于诸如询问询问$x$的$k$级祖先，我们用倍增先找到$x$的$hb(k)$级祖先$y$，这里$hb(k)$表示的是$k$的最高二进制位，之后对于$k'=k-hb(k)$，可以推出$k'<hb(k)$，而我们由性质2得到$y$所在的长链的长度至少为$O(hb(k))$，因此我们可以直接利用$y$所在长链顶部顶点的$A$、$B$数组直接查表得到。
查询树上最长k边路径
为每个长链顶部顶点创建一个与其所在长链的长度相同的数组，这里总的空间复杂度为$O(n)$。
之后我们处理非顶部顶点$x$时，我们就复用顶部顶点的预分配的数组，第i个元素记录x子树中由$i$条边组成总权最大路径的总权。
首先我们先递归处理长边连接的顶点，之后和通过短边连接的顶点的数组合并。
由于只有长链顶部顶点会对父元素产生与其长度相同的贡献，因此时间复杂度为$O(n)$。
树上路径查询
一般在线树上路径查询请求可以用LCT通吃，这里使用长链剖分可以做到$O(1)$回答静态请求。
比如我们要求查询路径上最大权的边。对于$u,v$路径，记lca为$t$我们可以将$u,v$之间路径切分成两部分，$u$到$t$和$v$到$t$。这里仅讨论$u$到$t$。记二者之间距离为$k$，首先找到$u$的$hb(k)$级祖先$a$，以及二者之间的最大权边，这里用倍增预处理就可以搞定了，时间复杂度为$O(n)$。接下来考虑$a$到$t$的路径，我们可以为$a$所在直链的顶部顶点$a'$预处理一条长度为直链长度的数组$A$，其中$A_i$表示$a'$的$i$级祖先到$a'$路径上的最大权边。当然如果$t$在$a'$和$a$之间，则在同一条直链上，此时我们可以根据直链分配连续编号，之后根据编号建立sparse table，这样就能保证$O(1)$级别的查询了。
双树问题
双树问题是指提供两颗树，在两棵树上做各种操作，且要满足一些约束条件。
题型1：给定两颗均包含$n$个顶点的树，第一颗树的边的颜色都为白色，第二颗树的边的颜色都是黑色。现在要求我们每次从第一颗树删除一条白边，并从第二颗树删除一条黑边，并将删除的黑边加入到第一颗树中，要求每次操作完成后第一颗树依旧是树（连通无环）。重复上述操作只到第一颗树的边全为黑，第二颗树无边。要求输出每次删除的白边和黑边。
这个问题有一个构造算法：
- 如果树2不存在黑边，则退出，否则进入步骤2。
- 从树2中任意删除一条黑边，边记作$b$。
- 将$b$加入树1，此时树1会出现一个唯一的环。出现的环中一定有白边（否则黑边成环意味着树2初始时一定有环），任意选择一条白边$w$，并移除。
- 回到步骤1。
很显然上面的算法是正确的，我们可以用LCT实现这个算法，时间复杂度为$O(n\log_2n)$。
题型2：给定两颗均包含$n$个顶点的树，第一颗树的边的颜色都为白色，第二颗树的边的颜色都是黑色。现在要求我们计算白边和黑边的最大匹配，白边和黑边相连当且仅当我们从将树1的这条白边和树2的这条黑边交换，两颗树依旧是树（连通无环）。要求输出最大匹配以及配对的白边和黑边。
考虑对于树2中的任意一条边$e_2=(u,v)$，从树2中删除并加入树1后，树2出现两个连通块，而树1出现一个环。
命题1：此时树1中从$u$到$v$的唯一路径上一定有一条边$e_1$，满足将$e_1$加入树2后树2连通。
证明：考虑从$u$到$v$的唯一路径，路径的两个端点在树2中处于不同的连通分块，因此，我们一定可以找到路径上一对相邻的顶点（又是间隙二分哦），顶点在树2中处于不同的连通分块。找到了这两个顶点，我们也就确定了$e_1$。
利用命题1，我们可以每次选择一条黑边，同时找到对应的白边。但是这时候问题出现了，同一条白边可能被多条黑边所匹配。解决方法就是我们每次找一条黑边，再在树1中找到一条可交换的白边，达成匹配后，我们将黑边从树2删除，并用白边代替它（但是我们始终保持树1不变）。这样我们能保证下一条树2中的黑边还能在树1中找到可以交换的白边，且这条白边一定没有被匹配过（否则再次被加入树2，出现了重边，此时一定有环）。
上面的流程保证了我们最大匹配一定是完美匹配。
暴力的做法就是$O(n^2)$。但是我们发现每次树1是不变的，因此我们可以提前在树1上计算倍增，之后在树1上查询路径的时候就可以二分路径找到端点属于不同连通块的边了。但是由于树2会不断变动，要维护它的连通关系，我们可以使用LCT或则动态图判连通算法，这样总的时间复杂度均为$O(n(\log_2n)^2)$。
但是这里有一个额外的技巧，我们发现每次选择一个端点为叶子的黑边，我们可以非常简单的判断连通性。对应的，当加入白边到树2中时，考虑到白边永远不会再被删除，因此我们可以保证白边的两个端点之后将一直保持连通，我们可以将两个顶点合并（合并并查集）。于是乎我们就提供了一个$O(1)$维护连通性的算法，总的时间复杂度降低到$O(n\log_2n)$。
Codeforces上有一道原题。
题目3：给定两颗都包含$n$个顶点的树，判断存在多少结点对$(a,b)$，其中$a<b$，且满足在一棵树中$a$是$b$的祖先，而在另外一颗树种$b$是$a$的祖先。
换言之问题实际上问，对于第一颗树来说，它有多少祖先是它在第二颗树上的后代。
我们可以按照第二颗树的dfs序重新为结点编号，这样每个在第二颗树上，子树形成连续区间。
现在我们可以dfs第一颗树，并维护所有祖先出现的位置，而要统计某个结点的在第二颗树的后代的出现次数，只需要统计范围和即可。我们可以用一个二叉索引树来维护，时间复杂度为$O(n\log_2n)$。
一类树上分割问题
题目1：给定一颗有$n$个顶点的树，其中$n\leq 10^5$，之后定义$f(i)$表示将树分解为若干个连通块，问最多能分解出多少个大小正好为$i$的连通块。要求输出$f(1),f(2),\ldots,f(n)$
这是Blogewoosh #3提出的问题和解法，我这里只是搬运而已。但是一部分内容是我自己的，与原文可能有些出入。
我们可以定义另外一个函数，记$g(i)$表示将树分解为若干个连通块，其中最多能分解出来大小至少为$i$的连通块数目。很显然$g(i)\geq f(i)$，但是由于任意大于等于$i$的连通块都可以从中切割出一个大小正好为$i$的连通块，因此$f(i)\geq g(i)$。因此总结得出$f(i)=g(i)$，即$f=g$。
于是乎问题就变成了我们希望将树分解为大小至少为$i$的若干个连通块。
首先很显然，我们对树进行dfs，并且同时做出贪心选择，如果子树中未分配的顶点总数加上自己，大小大于等于$i$，那么我们将自己与父亲的连边删除并得到一个大小不小于$i$的新连通块。这是一种贪心做法。
现在我们来证明贪心的正确性，假如存在最优解，使得存在这样一个顶点，其与父亲的连边未删除，且子树中未分配的顶点数目加上自己不小于$i$，那么我们可以删除与父亲的连边（如果操作后父亲大小不足，我们可以舍弃父亲），这样绝对不会使得最优解劣化。因此我们证明了贪心的正确性。
于是乎我们就得到了一个$O(n^2)$的暴力做法。
现在让我们来优化一下，注意到不等式$f(i)\leq \lfloor \frac{n}{i}\rfloor$一定成立，因此当$i\geq \sqrt{n}$时，$f(i)$只可能有$\sqrt{n}$种取值。因此我们可以分两种情况处理，对于$i\leq \sqrt{n}$，我们可以暴力计算，这里花的时间为$n\sqrt{n}$，而对于$i>\sqrt{n}$，由于$f$是递减函数，因此一定存在一个区间$[l,r]$（可能为空）和某个数$x<\sqrt{n}$，使得$f(l)=f(r)=x$。我们可以用二分来加速计算。
上面的优化后的算法的时间复杂度为$O(n\sqrt{n}\log_2n)$，但是实际上我们可以选择暴力计算到$\sqrt{n\log_2n}$，这样真实的时间复杂度就会降低到$n\sqrt{n\log_2n}$。
上面提供了一种有通过可能性的算法。
下面我们再来讨论一种更快速的方式。
考虑当树是毛毛虫状的，即除了叶子结点外，其余顶点恰好形成一条路径（主干），这时候我们就可以用线段树维护它，之后对于块大小至少为$i$时，我们可以用最多$\frac{n}{i}$次二分法（在线段树上二分），找到树最多能切分为多少段，这样所需的时间复杂度为$O(\frac{n}{i}\log_2n)$。很显然，当$i$很小的时候，算法的速度反而变慢了，但是观察总的性能，我们会发现为$O(n(\log_2n)\sum_{i=1}^n\frac{1}{i})=O(n(\log_2n)^2)$，反而变快了有木有。
当然上面这个算法仅适用于毛毛虫状树。但是仔细思考普通树和毛毛虫状树区别是什么，实际上在贪心的过程中，毛毛虫状树我们只需要处理主干，但是普通树，如果存在另外一个分支大小超过$k$，那么我们必须同时处理这个分支。因此我们可以将所有大小超过$i$的分支从原来的树中分离出来，独立计算贡献，最后统计到结果中去。那么分支不会很多吗？不会多的，在要求连通块大小至少为$i$的前提下，一棵树的分支数最多为$\frac{n}{i}$，而总的流程中，最多存在$O(n\log_2n)$个分支。
因此到此我们就得到了整个算法。我们可以对树进行轻重链剖分，之后将每条重链放到线段树上进行维护。每当我们发现分支小于当前的要求的时候，我们就将分支合并回原本分出的位置。在线段树上我们可以维护动态规划，来支持二分操作。每次二分的时间复杂度为$O(\log_2n)$，而每次分支对主干的贡献也为$O(\log_2n)$，因此总共的时间复杂度为$O(n(\log_2n)^2)$。
树上路径统计问题
问题1：给定一株拥有$n$个顶点的树，每个顶点都有点权，要求回答$m$个请求，每个请求给定$u,v$，要求计算$u$到$v$的唯一路径上所有顶点的点权和
这个问题做法非常多。简单的就是动态树或者树链剖分。或者我们可以发现每条唯一路径都有一个深度最小的顶点$lca(u,v)$，所以问题也可以转换成差分。
时间复杂度最小可以优化到$O(n)$（利用线性计算LCA的技术）。
问题2：给定一株拥有$n$个顶点的树，每个顶点都有点权。给定一个数$m\leq 10^6$，要求回答树上存在多少条路径，满足路径上顶点的权重之和正好等于$m$，$(u,v)$和$(v,u)$认为是不同的路径，如果$v\neq u$
问题1中提出的解决路径统计的技术已经无法解决问题2了，因为它们只能支持逐路径查询，但是这里路径总共有$n^2$条。
首先我们可以先提前计算掉有多少个顶点的权重恰好等于$m$，而之后我们只需要考虑那些长度至少为2的路径有多少条即可。
一种最简单的方案就是树上DP，但是由于点权的范围可能比较大，因此我们不能以数组来存DP，而需要借助哈希表。而在计算某个顶点的贡献的时候，我们需要合并所有孩子的哈希表，这个可以借助启发式合并，总的时间复杂度为$O(n\log_2n)$，但是由于用了哈希表，因此常数较大。
第二种方式就是利用DSU on tree，这样做的好处就是可以摆脱哈希表的常数。在顶点继承重孩子的数据的时候，我们需要将所有数据的权重增加该顶点的权重，这里我们可以通过维护一个全局变量实现。总的时间复杂度为$O(n\log_2n)$，常数较小。
第三种方式就是利用重心剖分。我们每次都找到重心，并暴力统计经过重心的路径的贡献。在计算完重心后，递归处理重心下的所有子树。这样做的时间复杂度同样也是$O(n\log_2n)$，但是常数适中。
这三种方式各有优劣：
- 第一种方式好想好写好调，但是就是容易TLE或MLE。
- 第二种方式跑得快，就是必须要求顶点可以快速继承孩子的数据，使得只能在一些特殊问题中发挥作用。
- 第三种方式泛用性极强（不要求继承数据，每次都可以清空重来），但是代码篇幅会较大且容易写错，而且跑的也没第二种方式快。
问题3：给定一株拥有$n$个顶点的树，每个顶点都有点权。现在定义路径$(u,v)$上的顶点的权重分别为$x_1,x_2,\ldots,x_k$，定义$f(u,v)=\sum_{i=1}^k(k-i+1)x_i$，要求计算$f$的最大可能取值
首先我们来考虑如何计算$f(u,v)$，考虑路径中某两个相邻顶点对$(x,y)$，我们可以通过合并$(u,x)$和$(y,v)$的信息来得到$(u,v)$。简单的思路是$(y,v)$对$(u,v)$的贡献仅为$f(y,v)$和$(y,v)$长度，而$(u,x)$对$(u,v)$的贡献仅为$f(u,x)$与$(u,x)$上顶点的总权值。因此我们可以写出$f(u,v)=f(u,x)+f(y,v)+S(u,x)L(y,v)$，其中$S(u,x)$表示路径总权，而$L(y,v)$表示路径总长。
我们可以特殊的选取$x$为$lca(u,v)$，这样我们就能以动态规划的方式解决这个问题了。我们可以考虑按顺序处理子树，并用凸包技巧维护子树信息。
现在我们可以考虑问题2中提出的三种算法，看是否能用来解决这个问题。
首先如果我们使用树上DP的方式，那么每个顶点都需要处理整个子树的信息，这样时间复杂度就为$O(n^2\log_2n)$，还不如暴力。
如果我们使用DSU on tree技术，那么问题来了，如果继承重孩子的数据呢，因为我们必须修改凸包技巧中存储的一阶多项式。
现在考虑最后的重心剖分，你会发现由于每次都重新建立凸包技巧，因此我们不需要考虑如何继承的问题。因此重心剖分是可行的，总的时间复杂度为$O(n(\log_2n)^2)$。
提供CF原题。
问题4：给定一个拥有$n$个顶点的树，每条边都有一个颜色（黑色或白色）。对于一条路径，称其为良好的，当且仅当路径中的黑边数$b$与白边数$w$满足$2w\geq b\land 2b\geq w$。现在要求统计所有$n^2$条路径中，有多少路径是良好的。其中$1\leq n\leq 10^5$
很显然只有一个顶点的路径永远是良好的，我们先不统计它们，最后结果加上$n$即可。
由于是所有路径的查询，因此很自然可以想到用点分治。找到树的重心，统计所有过重心的路径，并对重心下的子树递归处理。
现在剩下的问题是，我们如何处理判断过重心的路径是良好的。暴力当然是没有意义的（这和暴力就一样了），我们可以发现路径可以分成两部分，第一部分就是从某个子树到重心，另外一部分就是从重心到某颗子树。我们用$(x,y)$表示第一部分的路径，意思是拥有$x$条白边和$y$条黑边，同理用$(a,b)$表示第二部分的路径。现在我们可以发现两部分合成的路径是良好的，必须满足$2(a+x)\geq b+y$，我们稍加转换可以得到新的公式$2a-b\geq y-2x$，因此我们可以把路径第一部分的$y-2x$丢到BIT或其它RMQ结构中，这样在枚举第二部分时，可以$O(\log_2n)$统计有多少第一部分满足条件。当然仅仅满足这个条件还是不够的，还需要满足$(a+x)\leq 2(b+y)$。一个条件简单，两个条件就很麻烦了，但是注意到满足第一个条件的集合和满足第二个条件的集合的并集一定是全集，因此可以用简单的容斥进行处理。
记$A$为满足第一个条件的第一部分路径组成的集合，$B$为满足第二个条件的第一部分路径组成的集合，$S$为全集，我们要求的是:
\[|A\cap B|=|A|+|B|-|S|\]对第二个条件也可以转换为$2b-a\geq x-2y$的形式，我们用同样的RMQ技术维护即可。
总的时间复杂度为$O(n(\log_n)^2)$。
提供一道题目。
题目5：给定一颗拥有$n$个顶点的树，每个顶点都有一个编号。现在要求在线回答$m$个请求，每个请求指定两个顶点$u,v$以及一个整数$k$，要求找到$u,v$之间唯一路径上第$k$小的顶点编号。
提供一道题目。
我们为每个顶点维护一个权值线段树，记录从根到这个顶点的路径上每个编号的出现次数。可以发现如果我们这里借助持久化技术，可以保证时空复杂度为$O(n\log_2n)$。
之后对于每个请求，记$l=lca(u,v)$，$p_l$为$l$在树上的父亲。那么二者路径上的统计关系可以通过$u+v-l-pl$（这里表示的线段树的加减法）来获得。我们不需要完全算出整颗树，只需在上面二分即可，这样只会处理最多$O(\log_2n)$个顶点而已。
总的时间复杂度为$O((n+m)\log_2n)$。
题目6：给定一颗拥有$n$个顶点的树,每个顶点都有一个编号。现在要求在线回答$m$个请求，每个请求指定两个顶点$u,v$以及一个整数$l,r$，要求找到$u,v$之间唯一路径上在$[l,r]$区间中的最小的出现奇数次的编号，如果不存在，则输出$-1$。
提供一道题目。
我们为每个编号进行哈希，哈希到某个$64$位整数。之后我们为每个顶点维护一个线段树，线段树中记录从根到这个顶点的所有编号的哈希信息，哈希信息通过异或合并在一起。这里通过持久化可以做到$O(n\log_2n)$的空间和时间复杂度。
之后对于每个查询操作，记$l=lca(u,v)$，$p_l$为$l$在树上的父亲。那么二者路径上的统计关系可以通过$u\oplus v\oplus l\oplus pl$（这里表示的线段树的异或运算）来获得。我们不需要完全算出整颗树，只需在上面二分即可，这样只会处理最多$O(\log_2n)$个顶点而已。
下面计算一下冲突的概率。可以发现一个区间异或和为$0$的时候，其中某个编号出现奇数次的概率为$\frac{1}{2^{64}}$。而一个区间异或和非$0$的时候，则必定存在一个编号出现奇数次。因此我们这边失败当且仅当在执行二分操作的时候，某个区间异或和为$0$，但是实际上某个编号出现了奇数次，即每次操作成功的概率为$1-\frac{1}{2^{64}}$。而总共有$O(m\log_2n)$次的二分操作，记$A_i$为第$i$次成功的实验集合，成功概率为$\mathrm{Pr}(\land_iA_i)=1-\mathrm{Pr}(\lor_i\overline{A_i})\geq 1-\sum_{i}\mathrm{Pr}(\overline{A_i})=1-\frac{m\log_2n}{2^{64}}$。非常大的。
LCA算法及应用
在有根树中，两个顶点的LCA是指二者的所有公共祖先中深度最大的那个。
LCA的性质：
- 两个顶点$u,v$的唯一路径一定经过它们的LCA，且它们的LCA是$u,v$路径上深度最小的顶点。
LCA算法的实现方式大概有以下几种：
- 离线tarjan算法，时空复杂度为$O(n)$。
- 树上倍增，预处理时空复杂度$O(n\log_2n)$，之后每个请求处理的时间复杂度为$O(\log_2n)$。
- ST表+树上DFS序，预处理时空复杂度$O(n\log_2n)$，之后每个请求处理的时间复杂度为$O(1)$。
- Schieber Vishkin算法，预处理时空复杂度$O(n)$，之后每个请求处理的时间复杂度为$O(1)$。
- Link Cut Tree做法，允许换根和加边删边，预处理时间复杂度$O(n\log_2n)$，空间复杂度$O(n)$，之后每个请求处理的时间复杂度为$O(\log_2n)$。
LCA算法还可以用于解决下面一类问题：
- 判断某个顶点$x$是否落在$u,v$的唯一路径上：首先$x$一定处在$lca(u,v)$子树内，且$x$一定是$u$或$v$的祖先。
- 判断$x_1,y_1$的路径与$x_2,y_2$的路径是否有交点：两条路径假如有交点，记任意交点为$z$，很显然$z$一定是$x_1$或$y_1$的祖先，且$z$还是$x_2$或$y_2$的祖先。因此可以推出$lca(x_2,y_2)$一定是$x_1$或$y_1$的祖先，且$lca(x_1,y_1)$还是$x_2$或$y_2$的祖先。
- 计算$u,v$的路径长度：长度为$depth(u)+depth(v)-2\cdot depth(lca(u,v))$
子树划分问题
题目：给定$n$个顶点构成的树，以及某个给定的正整数$k$，要求将树划分成若干个区域，每个区域中顶点数目都落在区间$[k,3k]$之间，或者报告无解。且我们需要为每个区域设置一个中心顶点，中心顶点可以不属于这个区域的任何顶点（但是它必须属于某个特定的区域），但是这个区域到自己的中心顶点所经过的路径上的所有顶点（除了最后一个）都需要属于这个区域（换句话说，如果中心顶点属于当前区域，那么当前区域连通）。
首先我们先证明如果树中拥有超过$k$个顶点，那么树一定能被划分。
设树的大小为$T$，当$k\leq T\leq 3k$的情况下，我们可以将整个子树作为一个连通块，即此时树能被正确划分。现在考虑$T>3k$的情况。我们可以这样做，首先找到树的重心，接下来分若干种情况讨论。
- 如果重心的重孩子大小小于$k$，我们可以利用一种贪心算法，不断向当前构建的子集添加重心下的子树，直到子集大小超过$k$，就开始构建下一个子集，这些构建得到的子集的中心都是重心。现在可能最后构件的子集大小小于$k$，此时一定有构建好的某个大小范围为$[k,2k)$的区域，我们将当前区域以及根顶点全部加入这个区域中，很显然此时区域的大小范围为$[k,3k)$。
- 如果重心的重孩子大小大于$k$，且所有大小小于$k$的子树大小之和不小于$k$，我们可以将所有大小大于等于$k$的孩子递归调用递归流程，并从重心上删除这些子树。最后我们重新对孩子调用点分治即可，很显然所有调用递归的子树规模都减少了至少一半。
- 否则重心的重孩子大小大于$k$，且所有大小小于$k$的子树大小之和小于$k$，这里我们从所有大小不小于$k$的子树中，选择非重心的任意一个子树保留，其余大小不小于$k$的子树调用递归处理掉，最后递归处理剩下的子树。现在剩下的顶点数应该小于等于$T-\frac{T-b}{2}$，注意到$T>3k$，因此最多为原树大小的$\frac{2}{3}$。
上面的流程给出了一个分治的方案，且每次调用分治，子树的规模都至少缩小为原来的$\frac{2}{3}$。因此时间复杂度应该为$O(n\log n)$。
一类树划分问题
有一类问题，是给出一颗树$T$，之后对每条边$e$计算删除它后得到的两棵树$A_e,B_e$，要求我们求$\sum_{e\in T}f(A_e,B_e)$。
这类问题假如直接暴力枚举每条边，之后对得到的两棵树进行DFS，这样的时间复杂度会达到$O(n^2)$。但是可以发现每条边一定连接父子两个顶点，因此如果我们维护两棵树的实时信息，那么当我们沿着边从父亲移动到孩子，两棵树的变化量非常小。这也给我们提供了一种维护增量变换信息的思路来优化时间复杂度。
举个例子：给定一颗树，每个顶点的编号从$1$到$n$。要求我们计算对每条边删除后得到的两颗子树最大值之积的和。换言之，计算$\sum_{e\in T}\max_{a\in A_e,b\in B_e}a\cdot b$。
用我们提到的方法，我们可以为每个顶点$u$，计算出以$u$为根的子树中最大编号，记为$Sub(u)$。
之后考虑如何计算结果。我们对树进行dfs，假设我们抵达了某个顶点$u$。我们实时维护在删除了$u$子树后其余顶点组成的树$F$中的最大值$M$。之后我们考虑枚举子边$(u,v)$，很显然此时$(u,v)$边删除后，记$u$所在的子树为$A_e$，而$v$所在的子树为$B_e$。很显然$B_e$的信息是已知的（即$Sub(v)$），那么现在我们需要计算的就是$A_e$。可以发现$A_e$可以是由三部分组成的，$u$本身，$F$，$u$的其余孩子。其中$u$的其余孩子信息比较难统计（比如$u$的孩子非常多）。这里有一个简单的技巧，就是维护一个前缀和和后缀和，那么$u$的其余孩子实际上就是由前缀和和后缀和合并后可以快速计算出来。
在上面问题中时间和空间复杂度为$O(n)$。
题目1：给定一棵包含$n$个顶点的树，其中一些顶点是白色的，一些顶点是黑色的。要求从树中删除一条边后再加入一条边，要求形成一颗新的树，要求让互相连通的白色顶点对尽可能多。两个白色顶点对是连通的，当且仅当两者之间的唯一路径上的顶点都是白色顶点。其中$1\leq n\leq 10^6$。要求输出最多的连通的白色顶点对数（(a,b)和(b,a)认为是相同的顶点对）
这个问题就用到了上面提到的技术。如果树上所有白色顶点对都已经连通了或者根本不存在白色顶点对，那么问题就非常简单。这里不细讲这种情况。
下面我们考虑至少存在两个白色顶点是不连通的情况。这时候我们可以断定被删除的边两端至少有一个黑色顶点，而加入的新边两端都是白色顶点对。有了这个断言，我们就可以非常简单的解决这个问题了。
首先我们为每颗子树预先计算出其中最大的白色顶点连通块大小。那么我们从上至下dfs的时候，实际上可以通过枚举四种情况（父边连接的子树、前缀、后缀、自己）来快速计算出边的上下子树信息。并且我们不必考虑那些两端都是白色顶点的边以及删除它们带来的影响。
时间复杂度为$O(n)$。
树上匹配问题
题目1：给定$n$个顶点的树（$n$是偶数），我们要将所有顶点两两配对，其中顶点$u$和顶点$v$配对的权值为$dist(u,v)$，即两个顶点在树上唯一路径中的边数。现在要求将所有顶点两两配对，且要求计算最大的可能权重和最小的可能权重。
我们知道树上距离的计算公式为$dist(u,v)=depth(u)+depth(v)-2\cdot depth(lca(u,v))$。记所有分组的集合为$P$，则总权重为：
\[\begin{aligned} W(P)&=\sum_{(u,v)\in P}dist(u,v) &=\sum_{(u,v)\in P}depth(u)+depth(v)-2\cdot detph(lca(u,v)) &=\sum_{v\in V}depth(v)-2\cdot \sum_{(u,v)\in P}depth(lca(u,v)) \end{aligned}\]因此我们要让权重最大，需要让$\sum_{(u,v)\in P}depth(lca(u,v))$最小。对应的要让权重最小，需要让$\sum_{(u,v)\in P}depth(lca(u,v))$最大。
在求最大的情况，我们可以对树进行DFS，并尽可能将LCA设置为当前遍历的顶点。而在求最小的情况，我们同样对树进行DFS，但是尽可能在遍历子树的时候就将子树中的顶点配对。
时间复杂度为$O(n)$。
实际上这里要让权重最大，我们可以直接找到树的重心即可，将重心作为根，这时候所有配对顶点的lca都是根。
题目2：给定$n$个顶点的树（$n$是偶数），我们要将所有顶点两两配对，其中顶点$u$和顶点$v$配对的权值为$dist(u,v)$，即两个顶点在树上唯一路径中的边数。现在要求将所有顶点两两配对，且要求所有配对的总权值正好为$k$。要求输出配对方案。其中$2\leq n\leq 10^5$
提供一道题目。
我们可以先找到树的重心，之后我们将重心作为树根。我们不考虑配对的权重，而是通过考虑每条边的贡献。考虑一条边$e$，其将树分成$x$和$n-x$两部分。可以发现配对的顶点落在不同的部分的配对数的奇偶性与$x$相同，记$f(e)=x\pmod 2$，记$g(e)=\min(x, n-x)$。
考虑题目$1$中我们让总权最大和最小的算法，我们可以证明最小权值为$m=\sum_{e} f(e)$，而最大权值为$M=\sum_{e}g(e)$。同时$m$和$M$拥有相同的奇偶性。且$k$与$m$和$M$拥有相同的奇偶性是有解的必要条件。
下面我们考虑在$m\leq k\leq M$且$k$与$M$具有相同奇偶性的前提下，进行求解。
可以发现如果我们选择根下的最大一颗子树$T$，并从中删除任意两个顶点，那么根依旧是树的重心（一般情况下，这是不满足的，但是需要注意$n$是偶数）。我们具体删除那两个顶点呢，我们选择深度最大的叶子，之后从从它的父亲列表删除两个孩子（如果孩子只有一个，就将父亲一同删除），可以发现$T$依旧是一棵树。但是可能这样会导致当前的总权值低于$k$，这时候我们可以暴力找到一个深度恰好的顶点，删除它和它的某个孩子即可。
树上监视问题
题目1：给定$n$个顶点的树，现在要求在一些顶点上放置$k$个监视器。其为每个顶点$u$维护一个向量$v^{(u)}=(v^{(u)}_1,v^{(u)}_2,\ldots,v^{(u)}_k)$。其中$v^{(u)}_i$表示的是监视器$i$到顶点$u$的最短距离。我们希望让所有顶点对应的向量都不同，问$k$的最小值是多少，并且求出一组放置方案。
首先任意顶点$u$，我们将$u$作为树根。考虑$u$的所有子树。可以发现如果同时有两个子树中都不放监视器，那么这两个子树的根的向量一定相同。因此我们可以发现，对于任意树，其子树中最多有一个子树没有放监视器。
我们可以在树上进行一次dfs。之后如果我们发现有多于一颗子树没有放监视器，我们就取任意一个没有放置监视器的子树中的叶子顶点，放入一个监视器。
如果有一个子树中没有放任何监视器，且$u$不是根顶点，这时候我们需要要求在$u$子树外其余顶点中至少放一个顶点。同时我们发现一些子树要求子树外顶点至少放一个监视器。我们将这个属性继承到当前顶点$u$中。我们永远不在当前顶点放监视器。
最后在处理根结点的时候特殊处理，因为此时根顶点依旧要求在外部至少放一个顶点，我们从中选择一个空叶子顶点放入监视器。
这个做法是$O(n)$的。
题目2：给定$n$个顶点的树，现在要求在一些顶点上放置监视器。每个监视器能监视距离到它所在顶点不超过$D$的所有结点。问至少需要放置多少个监视器，才能监视到树上所有顶点，其中$1\leq D\leq n\leq 10^5$
讲一个简单的贪心思路，就是每次枚举最深的未被监视的顶点$v$，找到它的$D$级祖先$u$，在$u$上放一个监视器。
先说明这个思路为什么是正确的。考虑到要监视$v$，那么必定在$u$的子树中需要放置一个监视器。但是如果这个监视器放置在$u$上，则不仅可以监视到整颗子树中的所有未被监视的顶点（因为$v$是最深的，其它未被监视的顶点的深度都小于它，自然也会被监视到），同时还能监视到最大范围的子树外的顶点。
但是仅靠这个思路，实现会有问题。因为这会导致最多$O(kn)$的时间复杂度，$k$为实际放置的监视器数量。
这里我们可以发现一个非常简单的事实，就是$k\leq \left \lceil \frac{n}{D}\right\rceil$。为啥呢，非常简单，我们考虑上面的过程，每次选择一个顶点放置监视器，并删除这个顶点为根的整个子树。可以发现每次都至少会删除$k$个顶点（除了最后一次）。了解了这个性质，就可以为每个顶点维护一个距离最近监视器的距离。很显然每次放置监视器后更新所有周边顶点的时候，如果发现这个顶点距离之前最近的一个顶点的距离不大于到新监视器的距离，就可以跳过这个顶点。因此每个顶点最多被更新$D$次，总的时间复杂度为$O(\min(D,\left \lceil \frac{n}{D}\right\rceil)n)\leq O(n\sqrt{n})$。
但是实际上如果我们继续观察，可以发现一个顶点$v$上放监视器，当且仅当其子树中存在一个为被监控的顶点，距离$u$为$D$，或者$u$为根。这提供了一个DP的思路。具体做法就是记$A(u)$表示在以$u$为根的子树中的监视器数，$B(u)$表示以$u$为根的子树中的距离$u$最远的未被监视的顶点的距离，$C(u)$表示以$u$为根的子树中的距离$u$最近的放置监视器的顶点的距离。这样一次dfs就可以得到所有的状态，时间复杂度为$O(n)$。
度数转树问题
题目1：给定$n$个顶点，其中$2\leq n\leq 10^5$。以及每个顶点的度数，$d_1,\ldots,d_n$，满足$1\leq d_i$，且$\sum_{i=1}^nd_i=2(n-1)$。要求找到任意一颗树。
我们考虑两个顶点$i$和$j$合并的意义，此时两个顶点合并后的连通块的度数为$d_i+d_j-2$。并且如果不是最后一次合并，那么度数$d_i+d_j-2$就不能为$0$，换言之，我们不能把两个度数都为$1$的顶点合并。
所以下面就是我们的算法：
- 我们每次挑选两个度数最大的联通块合并。
下面我们通过维护不变式$\sum_{i=1}^kd_i=2(k-1)$且$1\leq d_i$，其中$k$是剩余的连通块数，来证明上面的算法是正确的，
当$n>2$的时候，我们可以断言至少有一个顶点的度数超过$1$，否则$\sum_{i=1}^kd_i\leq k<2(k-1)$，与前提相悖。这时候合并后的连同块的度数至少为$1$，所以我们的不变式还是成立的。而当$n=2$的时候算法是正确的，此时我们成功得到了一颗树。
可以同时发现$1\leq d_i$，且$\sum_{i=1}^nd_i=2(n-1)$是树存在的充分必要条件。
题目2：给定$n$个顶点，其中$2\leq n\leq 10^5$。以及每个顶点的度数，$d_1,\ldots,d_n$，满足$1\leq d_i$，且$\sum_{i=1}^nd_i=2(n-1)$。要求找到一颗匹配最大的树。
根据题目$1$，我们发现$1\leq d_i$，且$\sum_{i=1}^nd_i=2(n-1)$是树存在的充分必要条件。
我们在建树之前先贪心将未匹配的两个顶点两两合并。而度数为$1$的顶点不能与度数为$1$的顶点合并，因此我们可以先将度数为$1$的顶点和度数大于$1$的顶点合并，之后如果有多余的度数大于$1$的未匹配顶点，就将它们两两合并即可。
可以发现上述的算法不会影响树是否存在。
记$m$为度数为$1$的顶点的数目。可以发现最大匹配为$\min(n-m,\frac{n}{2})$。但是$n=2$的时候我们需要特殊判断，此时结果为$1$。
提供一道题目。
题目3：给定$n$个顶点，其中$2\leq n\leq 10^5$。以及每个顶点的度数，$d_1,\ldots,d_n$，满足$1\leq d_i$，且$\sum_{i=1}^nd_i=2(n-1)$。要求找一颗直径恰好为$D$的树，保证树存在。
提供一道题目。
如果$D=1$，则暴力处理。
否则我们可以考虑生成一颗直径最小的树，将顶点按照度数从大到小排序，之后以度数最大的顶点为根，以BFS的形式生成整颗树。
而现在给定了直径，因此我们应该在上面的流程中的某一步中断，并将剩余度数大于$1$的顶点追加到距离根最远顶点的尾部，剩余的度数为$1$的顶点再一一补上。
时间复杂度为$O(n\log_2n)$。
树上距离和
题目1：给定$n$个顶点和$n-1$条带权边，形成一颗树。现在记$dist(u,v)$表示顶点$u$和顶点$v$的距离。要求对于$i=1,\ldots,n$，计算$\sum_{j=1}^ndist(i,j)$。
跑一次dfs，令每个顶点维护子树大小，以及子树距离和。之后再跑一次dfs，传入子树外顶点到当前顶点的距离和和顶点数。这样加起来就可以了。
时间复杂度为$O(n)$。
题目2：给定$n$个顶点和$n-1$条带权边，形成一颗树。现在记$dist(u,v)$表示顶点$u$和顶点$v$的距离。要求对于$i=1,\ldots,n$，计算$\sum_{j=1}^ndist(i,j)^2$。
首先我们可以考虑距离公式：
\[dist(a,b)=depth(a)+depth(b)-2\times depth(c)\]其中$depth(x)$表示$x$的深度，而$c=lca(a,b)$。之后我们把公式套入得到：
\[\begin{aligned} dist(a,b)^2&=depth(a)^2+depth(b)^2+4\times depth(c)^2\\ &+2depth(a)depth(b)-4depth(a)depth(c)\\ &-4depth(b)depth(c) \end{aligned}\]考虑固定$a$，要计算$\sum_b dist(a,b)$，需要知道
\[\left\{ \begin{array}{l} \sum_b depth(b)^2\\ \sum_b depth(lca(a,b))^2\\ \sum_b depth(b)\\ \sum_b depth(b)depth(lca(a,b)) \end{array} \right.\]现在考虑我们维护了一个数组$A$，其中$A_i$表示$depth(lca(i,a))$。考虑我们处理完顶点$a$后，切换到顶点$a$的某个子结点$v$，那么$A$数组中仅$v$的子树对应的元素需要改变，统统变成$depth(v)$。如果我们在$A$中用顶点的dfs序号来作为下标，那么子树就对应一个连续的区间。这样我们就得到了$O(\log_2n)$切换顶点后维护$A$的技术。考虑$depth(b)^2$，$depth(b)$等其它状态也可以类似维护。总的时间复杂度为$O(n\log_2n)$。
但是实际上如果用题目$1$的方式，从父结点向子结点传入上部的信息，可以$O(n)$实现这个流程，但是对应的逻辑也更加复杂。
树上路径中最大权边
给定一颗$n$个顶点的树，要求回答$q$个请求，第$i$个请求要求查询$u,v$路径上最大权重的边的权重。其中$1\leq n\leq 10^6$，$1\leq q\leq 5\times 10^6$。
来源。
我们可以跑一次kruskal算法，在加入边$(x,y)$的时候，我们在创建一个新的顶点，将顶点的左孩子设置为$x$，右孩子设置为$y$，这样查询树上最大权的边等价于查询LCA。时间复杂度为$O(n\alpha(n)+m)$，这里我们可以基数排序来对边排序。
括号序列/dfs序
我们可以把一颗大小为$n$的树唯一的转换为一个长度为$2n$的括号序列，具体做法是对树进行遍历，进入某个顶点的时候，在括号序列尾部插入一个左括号，离开某个顶点的时候插入一个右括号。每个顶点对应一对匹配的左右括号。
同理一颗合法的括号序列（同时最左边的左括号和最右边的右括号匹配）也唯一对应一颗树。
括号序列的好处是我们可以把树作为字符串进行操作，而对于字符串我们可以将其丢到平衡树上进行加速，这样就可以实现$O(\log_2n)$级别的字符串各种骚操作，如果愿意舍弃一些内存，还能支持持久化。
来看看括号序列有哪些好，括号序列的表示方式，可以允许我们$O(\log_2n)$时间复杂度下完成下面所有操作：
- 子树的删除：我们可以删除一颗子树，对应的就是删除一段括号序列。
- 子树的插入：类似于删除，只不过变成插入一段括号序列。
- 查找k级祖先：考虑顶点$v$，要找它的深度为$h$的祖先，可以去二分找$v$右括号后第一个深度小于等于$h$的顶点，由于是在平衡树上二分，所以时间复杂度为$O(\log_2n)$。
- 查询lca：对于给定顶点$u,v$，如果二者为根的子树对应的括号子串有相交，那么较大的为lca。否则二者不相交，记$u$的括号对出现在前，那么在$u$的右括号到$v$的左括号之间的深度最小的顶点的父亲，就是它们的lca。找父亲，可以于用查找k级祖先提到的方法。
- 子树修改查询：对应的就是一段区间的修改查询。
- 查询两点距离：维护每个顶点的深度，查找lca后用距离公式计算。
- 查找dfs序最大/小的深度为$k$的顶点：这个实际上对应的就是查找最靠右深度大于等于$k$/最靠左深度大于等于$k$的顶点。直接在平衡树上进行二分即可。
但是这样维护括号序列是不能支持换根的，要换根需要用到euler tour tree。
提供一些问题：