树上问题

· · 个人记录

方法汇总

重心，直径的性质

$\text{DFS}$ 序：子树问题，链问题 树剖：链问题，子树问题 树上倍增：链问题 树上线段树合并：在树上维护数组 点分治：用于静态路径统计 树形 $\text{dp}$：有自下而上的推理方法，若父亲/祖先/子树外的节点会影响子树内部，把子树外的状态加入 $\text{dp}$ 的状态 $\text{dsu on tree}$：在树上维护数组 ## 一些重心，直径的性质 1. 在一个连通无向无环图中，从任意节点出发所能到达的最远节点，一定是该图直径的端点之一。 2. 若树的直径不唯一，则直径必定相交，并且相交于每条直径的中点。 3. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。 4. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。 5. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。 6. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。 7. 一棵树最多有两个重心，如果有两个重心，它们肯定相邻 ## DFS序的两个重要的用法 1. 求某个点到根节点的权值和。方法是：在每个点进的时候做加法，出的时候做减法。查询某个点只需要查询每个点进入的时候的和即可。 2. 求某个子树的权值和。方法是：在每个点进的时候做加法，并把值保存在当前节点，然后在每个点出的时候的和减去进的时候的和的值就是子树的权值和。 其实这两种用法很多时候是用来数颜色用的，也就是每个点带一个颜色，进入的时候在数组的那个颜色 $+1$，然后要查询某个颜色的情况。这个方法用来维护的信息一般需要有可减性 [CF1280C Jeremy Bearimy](https://www.luogu.com.cn/problem/CF1280C) 先考虑最小值，即让每条边被经过的次数尽量少。那么对于以 $u$ 为根节点的子树，设 $v$ 是它的儿子，那么可以得到：当 $siz_v$ 为偶数的时候，可以让子树内部匹配，而 $siz_v$ 为奇数的时候，边 $(u,v)$ 一定会被经过。 [P5838 USACO19DEC Milk Visits G](https://www.luogu.com.cn/problem/P5838) **解法一：离线** 对于一条路径 $(u,v)$，颜色 $c$ 的出现次数为 $cnt_u+cnt_v-cnt_{lca}-cnt_{fa[lca]}

将询问挂在对应节点上，\text{dfs} 的时候，我们每次进入一个点在序列中把这个点的颜色 +1，统计这个点当前颜色 c 的数值，回溯的时候这个点的颜色 -1

时间复杂度为 O(m\log n)

解法二：树剖+二分

树剖之后，询问的每条路径都被剖成了 O(\log n) 条重链，对于每条重链，我们相当于要询问某一个 \text{dfn} 序的区间 [dfn[top[u]]+dfn[u]] 中是否存在某个颜色

我们可以先预处理，对于每个颜色 把所有颜色为 的节点的 \text{dfn} 序存到一个 \text{vector} 中，然后问题就变为这个 \text{vector} 中是否有一个数在某个区间中，我们就可以用二分查找判断了

时间复杂度为 O(m\log^2 n)

CF1528C Trees of Tranquillity

这个点集 S 在第一棵树上肯定是在从树根到某个叶子的一条链上的。所以我们可以 \text{dfs} 棵树，然后去维护它们在第二棵树上的情况。

一个节点的子树在欧拉序中是一段区间。并且区间之间只有包含或不相交关系。所以我们可以在 \text{dfs} 第一棵树的时候去维护每个节点在第二棵树上的区间情况。我们需要维护最多有多少个两两不相交的区间。

当我们加入一个区间的时候，如果它被其他区间包含，我们就把包含它的区间删掉，换成它。如果它包含了原来的区间，那么加入它肯定不优，不加入它。

然后我们还需要记录每个点做的操作，在搜完一个点的时候回溯撤销操作。

上面的区间的维护我们可以用一个 \text{set} 来维护。复杂度为 O(n\log n)。

P2680 NOIP2015 提高组 运输计划

最大的最小很容易想到 二分答案。设最长路径长度为 maxn。对于二分的 mid，我们需要对于所有边权大于 mid 的路径找到一条边权至少为 maxn-mid 的公共边

这个就和第一个题目需要维护的东西非常相似了，所以我们可以通过树上差分 O(n) 验证

总的复杂度为 O(n\log A)

P7518 省选联考 2021 A/B 卷 宝石

树上路径问题先套路一下，s_i 到 lca，lca 到 t_i。然后分别考虑，先考虑向上的这条链，显然在这条路径上，每个权值尽量早的出现最优

我们考虑对给进来的 p_i 重标号一下，使之成为 1\sim c 的序列，同时对每个 w_i 值也进行对应的重标。那么我们对于每个点 u 可以倍增预处理 f_{u,i} 表示在 u 到根的链上权值为 w_u+2^i 的节点最近在哪里和 g_{u,i} 表示在 u 到根的链上权值为 w_u-2^i 的节点最近在哪里（为了处理下链）

这样我们就得到了上链最大能匹配到哪里，不妨设为 x。那么我们可以在下链上二分答案，下界为 x+1 ，上界为 c，在 v 到根的链上查找权值为 mid 的点，并利用 f2 不断往上跳，找到最大能匹配的后缀，看看是否能和前 1∼x 拼接在一起（答案显然具有单调性的，因为如果权值较大的点能和上链拼接在一起，那么权值较小的点更加可以和上链拼在一起了）

至于如何在线求一条到根的链上权值为 p 的点最深在可以用主席树维护

时间复杂度 O(n\log^2 n)

P5666 CSP-S2019 树的重心

考虑枚举每一条会被删去的边，删掉一条边后一棵树会变成两部分，设该边的两个端点为 x,y，其中深度较大的一点为 y，则这两部分分别为以 y 为根的子树和整棵树减掉以 y 为根的子树

具体可以用两次 \text{dfs} 和倍增实现

第一次 \text{dfs} 求出 zson_u,siz_u,p_{u,j}，p_{u,j} 表示 x 沿着重儿子走 2^i 步

第二次 \text{dfs} 换根,把上面数组的定义从以 1 为根改为以 x 为根。对于一条边,以下方的重心,可以直接倍增,可以跳的条件为上方的 siz\le sum/2，对于上方的重心,换根时记录信息,倍增方法一样