树？能吃吗？

· · 算法·理论

cnblogs

[2025-04-29] 新增树上依赖型背包。

[2025-06-11] 将最小生成树相关内容移到图论文章中。

LCA

先放一篇文章

这部分不算是一种算法，而是最近见到一些关于 LCA 的各种东西。原来自己并不理解 LCA。

首先讲一下 O(n \log n)-O(1) dfs 序 LCA 科技。

好神奇的做法！查询吊打倍增和树剖，常数全方位吊打欧拉序，就是空间没有树剖优秀。学了这个卡常的时候很有用。

以下内容参考 魏老师博客。

设树上的两个结点 u,v 的最近公共祖先为 d。

我们不得不使用欧拉序求 LCA 的原因是在欧拉序中，d 在 u,v 之间出现过，但在 dfs 序中没有。

以下内容假设 dfn_u < dfn_v。

设 v' 为 d 的子树包含 v 的儿子，显然 v' 在 u\rightarrow v 的 dfs 序之间。

并且对于 dfs 序而言，祖先一定出现在后代之前，所以任何 d 以及 d 的祖先均不会出现在 u\rightarrow v 的 dfs 序中。

所以我们只需要求 u \rightarrow v 的 dfs 路径之间深度最浅的点的父亲。

直接用上面的结论会查到 v 的父亲。可以特判，但是太麻烦了。

考虑令查询区间从 [dfn_u,dfn_v] 变成 [dfn_u+1,dfn_v]。

对于情况 1，u 显然一定不等于 v' 所以不影响，对于情况二显然正确。

综上，若 u=v LCA 显然，若 u \neq v 就查询 [dfn_u+1,dfn_v] 之间所有点的父亲中深度最浅的，可以 st 表实现。

代码很好写，但是注意 st 表的一些易错点。

int mnd(int x,int y){return (dfn[x]<dfn[y])?x:y;}
void dfs(int x,int fa){
    dfn[x]=++cnt,st[cnt][0]=fa;
    for(int i=hd[x];i;i=eg[i].nxt)
        if(eg[i].v!=fa) dfs(eg[i].v,x);
    return ;
}
int lca(int x,int y){
    if(x==y) return x;
    if((x=dfn[x])>(y=dfn[y])) x^=y^=x^=y;
    int d=l[y-x];
    return mnd(st[x+1][d],st[y-(1<<d)+1][d]);
}
signed main(){
    read(n),read(m),read(s);
    for(int i=1;i<n;++i)
        read(x),read(y),add(x,y),add(y,x);
    dfs(s,0); l[1]=0;
    for(int i=2;i<=n;++i) l[i]=l[i>>1]+1;
    for(int i=1;i<=l[n];++i)
        for(int j=1;j+(1<<i)-1<=n;++j)
            st[j][i]=mnd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    while(m--) read(x),read(y),writeln(lca(x,y));
    return 0;
}

P4211

在看见求 dep(LCA)，且 dep 定义为到根的边数或点数时可以想如下转化：两个点的 LCA 的深度是它们到根的路径重叠部分的长度，于是一个点到一个区间每个点的 LCA 的深度和，就是这个点到根的路径的每条边（或每个点），区间内经过这个边（点）的路径数量的和。

此题就是用这个结论，信息可减，把询问离线差分一下，扫描线即可。

P11364

用到了区间 LCA 的一些性质。结论是 \operatorname{LCA}[l,r] 是 \operatorname{LCA}(i,i+1)(l\leq i <r) 中深度最浅的。证明考虑 LCA 至少两个不同子树内存在区间内的点，所以至少有一对区间内相邻的点不在同一个子树内，它们的 LCA 就是区间 LCA。（不是很严谨的证明，只能感性理解一下了）。

考虑处理出所有 \operatorname{LCA}(i,i+1) 对应的最大区间，可以发现若区间合法子区间一定合法，问题转化为找这些区间与询问区间的交集 \geq k 的最大的 dep，分类讨论一下扫描线，具体细节见代码注释，不是这里讨论的重点。

虚树

有时候问题只与一些点和它们的 LCA 有关，此时如果遍历整棵树会浪费时间，但如果只看这些点就可以使用很多暴力做法。

虚树的构造就是用栈维护一个最右链，按 dfs 序从小到大加入点，分类讨论。

int build(){
    sort(h+1,h+k+1,cmp);
    int tp; stk[++top]=h[1];
    for(int i=2;i<=k;++i){
        int nw=h[i],lc=lca(nw,stk[top]); tp=0;
        while(dep[stk[top]]>dep[lc]){
            if(tp) add(stk[top],tp); tp=stk[top--];
        }
        if(stk[top]!=lc) stk[++top]=lc;
        if(tp) add(lc,tp); stk[++top]=nw;
    }
    tp=0;
    while(top){
        if(tp) add(stk[top],tp); tp=stk[top--]; //这一步别忘了
    }
    return tp;
}

P4103

就是虚树上做树形 dp。

对于两两路径和，考虑计算每一条边的贡献，即边权乘上边两端关键点个数的积。

虚树上一条边 (u,v)(v \in son_u) 的边权就是 dep_u-dep_v。

CF639F

先边双缩点，再建虚树，然后再在虚树上连边，缩点，然后看给定点集中的点是否都在一个强联通分量中。

代码细节较多。

P3323

首先看到 \sum m \leq 3\times 10^5 这种限制，结合它要求距离相关，考虑每次询问建出虚树。

对于在虚树中的点，容易用 bfs 或换根 dp 求出到它们距离最近的关键点。对于虚树上的一条边 fa_u \to u，里面可能有些点被省略了，而这些点应该有个分界点，上半部分属于 u 子树外的点，下半部分属于 u 子树内的点，当然也可能全部属于子树外或内。考虑求出 f_x,g_x 分别表示 x 子树内和外离它最近的点（pair 类型，还要存编号），两次 dfs 即可，然后在每条边的地方讨论一下找到分界点。

还有一些点既未出现在虚树上，也没出现在虚树的边上，但是这些点可以挂到离它们最近的虚树点或虚树边上省略的点上。对每个虚树点求出有多少点挂在上面，对于被省略的路径，也可以用原树的 sz 数组计算所有点数。

虚树都写完了才发现教练标了它是 10 级知识点

upd：NOI 大纲修订，虚树不是 10 级了！

点/边分治

当处理的问题与树的形态无关（比如统计某种路径的个数）时，考虑把路径分为经过根的和不经过根的，每次统计经过根的，然后再把树分为几个子树，在每个子树内找一个根做同样的统计。有点像 CDQ 分治。

统计经过某点的路径一般是将所有路径分为 2 段，然后计算拼起来的合法路径数量。

为了保证复杂度，每次定一棵树的重心为根。

点分树就是将一个点向它所有子树的重心连边重新构成的树，相当于将整个点分治的过程记录下来。

P6329

点分树模板题。

点分树，又名动态点分治，就是对于一些强制在线或带修多次询问的题目，不能离线处理所有询问，就将点分治的过程涉及到的半条路径都存下来，然后询问/修改的时候暴力跳分治中心，在存下来的数据结构上查询/修改。

本题若没有修改操作，显然可以将询问挂在点上然后点分治。每次分治将所有半路径按到分治中心的距离排序，查询都是一段前缀，双指针+前缀和似乎就可以做，当然也可以树状数组。现在带修，单点修改某个点的权值，那么考虑用树状数组维护。

建出点分树，然后对每个分治中心，存下维护它的所有半路径的树状数组（需要 vector 动态分配空间，总空间是 O(n\log n) 的）。然后存下每个分治中心的上一层，即点分树上的父亲 fa。每次暴力跳 fa 的次数是 \log 的，每跳到一个分治中心时在树状数组上查询或修改即可。

上面讲得较为粗略，实际上有不少细节，不过相对思路来说不重要了（bushi

P3241

这题点分树或边分树都能写。

边分治即每次找一条边尽量将树平均分为两棵子树，计算跨过这条边的答案，然后再对分成的两部分递归处理直到不存在边为止。

但是对于一般的树，这样可能会有一些问题。比如菊花图，无论选哪条边都只能分成一个大小为 1 的点和剩下的部分，于是复杂度达到了 n^2。所以在做题的时候会通过增加 O(n) 的点和边权为 0 的边将树变为每个点度数都 \leq 3 的，任意两点间距离与原来相同的新树再分治。

然而这题都保证度数 \leq 3 了，那直接上边分治啊！

若是没有强制在线，直接把询问挂在点上，每次分治的时候计算跨过当前边的点的贡献，树状数组维护即可。

强制在线考虑建出边分树，一次询问一个点涉及到的分治中心只有 O(\log n) 个。实现预处理每个分治中心的树状数组并存好，询问直接暴力在每个分治中心处查询即可。

CF715C

设当前分治中心为 rt，v 到 rt 的路径上距离为 d，u \rightarrow v 的路径满足条件

s(u,rt)\cdot 10^d + s(rt,v) \equiv 0 \pmod m

直接算的话左边的部分与 u 和 v 都有关，所以对式子稍作变形

s(u,rt) \equiv -\frac{s(rt,v)}{10^d} \pmod m

这样就可以用点分治做了。

在不少题目中可能会用到类似的方式，有时候变形要复杂很多，比如 P7283 这题要拆 \max 分讨。

AT_cf17_final_j

用到一个结论：求一个完全图的最小生成树，可以把所有边分成若干个边集，对于每个边集内求最小生成树，再把剩下的边保留再求最小生成树，可以得到原图的最小生成树。

点分治，考虑经过重心的路径产生的边集的 MST，然后加到最终的边集中，再跑 kruskal。

在这里边权算的是 x,y 到重心的距离 dis_x,dis_y 的和，对于真正的 dis(x,y) 只会偏大，而真正的 dis(x,y) 会在接下来的分治过程中被考虑到。上面提到的边集的 MST，显然就是最小的 dis_x 和其他点连边。

似乎也可以用 Boruvka 做，但不会。

CF150E

调的时候一直 TLE 以为哪常数大了或者按秩合并假了结果是点分治重心找错了

用处理众数的基本套路，先二分，然后将 \geq mid 的设为 1，< mid 的设为 -1，然后问题转化找求权值最大的长度在 [L,R] 的路径。

点分治，然后单调队列按秩合并。合并的时候把所有子树按子树内最大深度从小到大排序，然后先访问深度小的。这样每次初始化的复杂度是 O(maxdep)，由于排过序所以 maxdep 就是当前子树深度，这样总复杂度就是 O(n) 了，不然会被扫把卡掉。

P4183

很好，是我想不出来的智慧题。

有人说过如果你觉得某题是个好题，那说明你的水平和这题还差很远。

首先想出一个结论：是封上若干个叶节点，使得对于每个叶节点，Bessie 到它的距离 \geq 封上的点到它距离的最小值。（这个我自己想出来的）

考虑确定起始点的情况怎么做。称一个节点被封上，为在离他最近的叶节点处放一个农民，并且农民离他的距离 \leq 它到 Bessie 的距离。我们需要选若干个点封上，Bessie 不能经过封上的点，使得 Bessie 不能到达任意叶节点。求出离每个点最近的叶节点后可以 O(n) 树形 dp 求出。

考虑换根 dp继续挖掘性质，不考虑自己就是叶节点的情况，起点 x，考虑点 y，可以发现，若 y 点可以被封上，x \to y 方向上 y 的子树（即以 y 在 x 方向上连着的点为 y 的父节点时的子树）都可以被封上。证明可以自己画几个图分类讨论（分类为离 y 最近的叶节点是否在 x \to y 方向 y 的子树内）。

记 p_x 为离 x 最近的叶节点。也就是说，可以被封上的点，满足 dis(x,y) \geq p_y，并且这些点构成的形状是若干个树形的连通块，这些树状物的叶节点一定是原树的叶节点（根除外），而为了封上的点最少，我们要封的就是这些树状物的根节点。这样的根节点找起来比较麻烦，会涉及到其 x 为根时父节点的信息（即父节点不可以被封上），但是树状物中所有的节点只涉及到自己个 x，是好找的。考虑容斥，给每个节点赋上权值，使得一个树状物的权值和是 1。不难想到在自己处加上自己的贡献并在父节点处减去，也就是每个结点权值为 1-cntson_x 即 2-deg_x（根节点处，实际上有一条连向 x 方向的边，所以 cntson_x=deg_x-1）。

下面只需要找出所有 dis(x,y)\geq p_y 的路径，给 ans_x 加上 1-deg_y，可以淀粉质解决。这种方法在自己封自己的时候会有点小问题，但自己封自己当且仅当该点是叶节点，特判一下就行。

求 p_x 的方法很多，我只想到换根 dp，实际上一个多源 bfs 就解决了，真是唐的没边。

P6199

类似 Tree MST，先在第一棵树上淀粉质，边权转化为 val_x+val_y+dis2(x,y)（val 是到分治中心的距离，dis2 是第二棵树上 x,y 的距离）。

剩下的问题只和分治区域有关，考虑建出这些点在第二棵树上的虚树。

接下来问题完全转化为 Tree MST 那题了。可以考虑继续使用淀粉质，这样总的边数是 n\log^2 n，还要排序，时间复杂度不一定能接受。

题解给出更简单的做法：考虑求 mn_x 表示虚树上最小的 dis2(x,y)+val_y 的值并记录取到该值的 id_x=y，对于虚树上每条边 (x,y)，id_x 和 id_y 连边，对于每一个在分治区域内的点，x 和 id_x 连边。正确性感觉只能感性理解。

写代码的时候注意判一下当前点是不是建虚树引入的辅助点，如果是就没有第二类边。

目前最优解，好耶。

长链剖分

类似重链剖分，只是重链是以子树大小最大的儿子作为重儿子，而长链是以子树深度最大的儿子作为长儿子。

长链剖分的性质：

长链剖分一般用于优化与深度相关的树形 dp，一般状态为 dp[i][j] 表示以 i 为根的子树中深度为 j 的贡献。

P5903

树上 k 级祖先也算是长剖的经典应用。这个可以用倍增做到 O(n\log n)-O(\log n)，但长剖可以 O(n \log n)-O(1)，虽然感觉没啥用。

先预处理出 f_{i,j} 表示从 i 向上跳 2^j 步到达的点，长链剖分预处理出每个点对应的链顶和每个链顶向上向下跳 len （长链长度）的距离到达的点（这个总长度为 2n，可以用两个数组通过长链 dfn 连续的性质存）。

现在要查询 x 的 k 级祖先，考虑先向上跳 k'=2^{\lfloor \log_2 k \rfloor} 步到达点 x'，设 x' 所在长链长度为 d，显然 k'-k\leq k'，又由性质二 k'\leq d。这个时候再跳到链顶，也能证明链顶离目标点的距离不超过 d，根据预处理的结果可以一步跳到目标点。

CF1009F

经典的长链剖分优化 dp。

设 dp_{i,j} 表示 i 点子树中距离为 j 的点的数量，轻儿子的答案暴力更新，长儿子的答案继承到父节点。由于继承的时候整体后移一位并在前面加了一位，所以考虑倒着存，这样就只用在后面加一位了。

CF526G

运用到长链性质。

P4292

分数规划 + 长链剖分优化 dp（也可以像 CF150E 一样点分治+单调队列按秩合并）

二分答案，把所有边权减去当前二分的平均值，看长度符合要求的边权和最大的路径边权和是否大于 0。

设 f_{i,j} 表示以 i 为根的子树内，向下走 j 条边的最大边权和，长链剖分优化，然后线段树维护长链剖分。

梦熊 NOI 第 16 场 T1

分类讨论，分为三条路径都在 u 的子树内和两条在子树内，一条在子树外。

发现若子树内存在 \geq 2 条等长路径，设这样的路径长度最大为 l，那么 \sum l 是 O(n) 级别。证明考虑长链剖分，去掉长链后另一条路径的最大长度就是短链的最大长度，又要求等长，所以这两条路径的共同长度的最大值是短链长度，套用长剖的证明得到总长度线性。

对于第一类情况，直接长链剖分优化 dp 即可。

对于第二类情况，发现实时维护子树外与 u 不同距离的点并不容易（其实是能做的，但是我比较菜，不会），考虑一些更好想的做法。

子树外的东西是一条路径，考虑点分治将路径拆为两段，u 到分治中心和分治中心到其他子树中的某一点，长链剖分维护即可。

复杂度确实是 O(n\log n) 但是常数巨大，赛时被卡了，悲。

dsu on tree

这种看上去很暴力但是复杂度正确的算法真的好厉害！

每次都遍历所有子树再清空再遍历以父亲为根的树太浪费时间了，发现最后一个遍历的子树的答案可以不用清空直接继承给父亲，dsu on tree 的思想是考虑直接继承重儿子的答案。

由于每个点向上到根所经过的轻边条数不超过 \log n，所以每个点最多被遍历 O(\log n) 次，因此时间复杂度 O(n \log n)。

CF208E

dsu on tree 经典题。

把询问离线挂到树上然后对每个点算子树内所有深度的点的个数，对于轻儿子算完就清空，对于重儿子不清空保留。

感觉 dsu on tree 的题都差不多所以就不放了。动态维护加入和清空点的方式和莫队很像。

树上依赖型背包

刚学的 trick，用于解决选了某个点就必须选择其父节点的有根树上背包。

其时间复杂度的优化主要体现在把树拍为序列，回避了背包合并，每次都只加入单种物品。

为了方便，规定下面讨论的这棵树的节点编号等于 dfs 序。

首先树上背包做这个问题可以算出以每个点为根的子树的答案，其实我们并不需要这些，只需要求点 1 的答案。

考虑改写 dp 状态，设 f_{i,j} 表示考虑了 dfn \geq i 的点，体积和为 j 的最大价值。

在点 x，考虑其选或不选：

这样为什么能保证选出来的物品一定满足依赖要求，也就是不存在某点 x 和 fa_x 都考虑过，但是 x 选了但 fa_x 没选的情况？

考虑归纳证明，设 dfn 最大的点为 n，f_{n+1} 没有选点，一定合法。

对于点 x，若不选那么它的子树一定满足要求，而 f_{x+sz_x} 也合法，且考虑过的点不会受到 x 的子树不选的影响，所以结合起来依然合法。

若选 x，此时 x 的子树就可以选了，限制被放到了子树上。依旧分为 x 的子树内和子树外两部分，由于 f_{x+1} 合法，这两部分一定都合法。加上 x 后，第二部分不影响，第一部分容易发现依然合法。

然后模拟一下发现所有情况都可以被这样算到，正确性得证。

背包加法合并（瞎起的名字，与 O(V^2) 合并的区别参照多项式加法和多项式乘法）和背包加入单种物品（无论是 01 背包，多重背包还是完全背包）的复杂度都是 O(V)，所以这个算法的复杂度是 O(nV)。

P6326

朴素的树上背包 O(nm^2) 不能通过。

注意到要选出一个连通块，若钦定包含某个点，那么问题就转化为以这个点为根的树上依赖型背包。对每个点都做一次，复杂度降为 O(n^2m)，但依旧不能通过。

上述做法存在很多重复计算，钦定某一个点 x 为根后，已经考虑过所有包含 x 的连通块，下面只需要算不包含 x 的，也就是删去点 x，对剩下的每棵子树解决上述问题。

考虑点分治，每次钦定选取重心，然后递归解决重心的子树。时间复杂度 O(nm\log n)。

才发现原来点分治也可以分治连通块！