树相关问题

· · 算法·理论

树相关问题

本文讲的问题比较宽泛，凡是和树沾边的都有可能包含在里面。

前置知识

图论基础知识（图与树的定义和存储等），此处不再赘述。

## 最近公共祖先（LCA） ### 暴力 两种方式。 第一种：先让一个点向上标记，再让第二个点向上标记，第二个点向上标记时遍历到的第一个被标记过的点就是最近公共祖先。不妨称之为向上标记法或二次标记法。 第二种：先让靠下的那个点跳到和靠上的点一个高度，然后两个点一块跳直至相遇，相遇的点就是最近公共祖先。不妨称之为二次跳法。 两种方法单次最劣时间复杂度都是 $O(n)$。 ### 倍增法 相当于二次跳法的改进。 发现每次向上跳一下太慢了，我们考虑能不能多跳一点。倍增！我们预处理一个 $fa$ 数组，定义 $fa_{x,i}$ 表示节点 $x$ 的第 $2^i$ 个祖先。 具体跳的时候，假设要向上跳 $t$ 个位置，我们实际上跳的次数的 $BitCode(t)$ 次，也就是二进制下 $t$ 中 $1$ 的个数次。每次从大到小（从高位到低位）遍历，能跳就往上跳即可。 两次跳实际上都这么处理即可。区别在于，第一次两个点跳到了同一高度，第二次则是跳到了距最近公共祖先最近的儿子上。 为什么第二次不直接跳到最近公共祖先上呢？因为如果直接跳到了一个点上，只能说明在公共祖先上，但不能确保在最近公共祖先上。 单次时间复杂度 $O(\log n)$。 代码： ```cpp void dfs(int u,int pa){ //dfs求解每个点的深度 d[u]=d[pa]+1; //记录深度 fa[u][0]=pa; for(int v:e[u]){ if(v==pa) continue; dfs(v,u); } } void init(){ //初始化fa数组 H=__lg(n)+1; for(int j=1;j<=H;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; } int lca(int x,int y){ if(d[x]<d[y]) swap(x,y); //使更靠下的存为x for(int i=H;i>=0;i--) if(d[fa[x][i]]>=d[y]) x=fa[x][i]; //让x和y跳到同一位置 if(x==y) return x; //如果x和y已经重合，说明此时已经在公共祖先上 for(int i=H;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; //让x和y一块向上跳到距最近公共祖先最近的儿子上 return fa[x][0]; //跳到的是最近公共祖先的儿子 } ``` 树上倍增还可以维护其他信息：最大最小值，距离和，异或和等。 设我们要维护的信息存在 $f$ 数组中，则有下面的代码： 最大值：`f[x][i]=max(f[x][i-1],f[fa[x][i-1]][i-1])`\ 最小值：`f[x][i]=min(f[x][i-1],f[fa[x][i-1]][i-1])`\ 距离和：`f[x][i]=f[x][i-1]+f[fa[x][i-1]][i-1]`\ 异或和：`f[x][i]=f[x][i-1]^f[fa[x][i-1]][i-1]` 可以在维护 $fa$ 时同时维护上述信息或者单独维护。 ### Tarjan 算法 这是一种离线算法。本质是向上标记法的改进。 我们将 dfs 时节点的状态分为三种：$0$ 表示当前节点未被访问过；$1$ 表示访问中（未回溯）；$2$ 表示已经访问完（子树访问完）。实际实现时可以将 $1$ 和 $2$ 合并为一个状态。 我们每次访问一个点向上回溯时，利用并查集将其合并至最靠上的已经访问完（状态为 $2$）的父节点上。当一个点访问结束时，我们处理它的访问，如果另一个点被访问过，则二者的最近公共祖先就是另一个点并查集存的点。画个图不难理解。 设查询次数为 $q$，不考虑并查集的话复杂度是 $O(n+q)$ 的。 代码： ```cpp int vis[N]; //0未访问,1访问中(未回溯),2访问完 int Find(int x){ if(fa[x]==x) return x; return fa[x]=Find(fa[x]); } void tarjan_lca(int u){ vis[u]=1; fa[u]=u; //初始化fa for(int v:e[u]){ if(vis[v]) continue; tarjan_lca(v); fa[v]=u; } for(int i=0;i<ask[u].size();i++){ int v=ask[u][i].v,id=ask[u][i].id; if(vis[v]==2) ans[id]=Find(v); } vis[v]=2; } ``` ### RMQ + 欧拉序 **时间戳**：按照 dfs 遍历，节点第一次被访问的顺序。用 $dfn_u$ 表示 $u$ 节点时间戳。 **dfs 序**：表示从根节点开始对树进行 dfs 遍历的节点序列。相当于将节点编号按照时间戳排序。如果使用 $a_i$ 表示该节点序列，则有 $\large a_{dfn_u} =u$。~~（这一坨下标套下标真难看。）~~ **欧拉序**：表示从根节点对树进行 dfs 遍历，再回溯至根节点的节点序列。长度为 $2n-1$。 求欧拉序的代码放一下。 ```cpp void dfs(int u,int fa){ //求欧拉序 dfn[u]=++cnt; //记录时间戳 a[cnt]=u; //记录欧拉序 d[u]=d[fa]+1; //记录节点深度 for(int v:e[u]){ if(v==fa) continue; dfs(v,u); a[++cnt]=u; //回溯时的记录 } } ``` 记录下欧拉序之后，求节点 $u$ 和 $v$ 的最近公共祖先就是欧拉序区间 $[dfn_u,dfn_v]$ 中深度最小的节点，可以使用 ST 表来做到 $O(1)$ 查询。不过 ST 表预处理是 $O(n\log n)$ 的。 直接放全部代码吧。 ```cpp void dfs(int u,int fa){ //求欧拉序 dfn[u]=++cnt; //记录时间戳 a[cnt]=u; //记录欧拉序 d[u]=d[fa]+1; //记录节点深度 for(int v:e[u]){ if(v==fa) continue; dfs(v,u); a[++cnt]=u; //回溯时的记录 } } int g(int u,int v){return d[u]<d[v]?u:v;} int f[N<<1][20]; //f[i][j]表示欧拉序中从i开始长度为2^j的区间中深度最小的节点编号 void ST(){ for(int i=1;i<=cnt;i++) f[i][0]=a[i]; for(int j=1;(1<<j)<=cnt;j++) for(int i=1;i+(1<<j)-1<=cnt;i++) f[i][j]=g(f[i][j-1],f[i+(1<<(j-1))][j-1]); } int lca(int u,int v){ if(dfn[u]>dfn[v]) swap(u,v); int k=__lg(dfn[v]-dfn[u]+1); return g(f[dfn[u]][k],f[dfn[v]-(1<<k)+1][k]); } ``` ## 树的重心 ### 定义 如果一棵树中将一个点删除后，分开的各个子树中节点数最大的最小，则该点为重心。 ### 性质 - 最多两个且相邻。 - 重心所有子树大小不超过总节点数的一半。 - 树上所有点到重心的距离和是所有点到某点距离和中最小的。 ### 求法 我们直接 dfs 求一个点的子树大小，同时记录该点最大子树的大小，记下来重心就行。 ```cpp int root,siz[N],maxp[N],sum; //重心，子树大小，删除当前节点后最大子树大小，当前子树总节点数 void dfs(int u,int fa){ //求重心 siz[u]=1;maxp[u]=0; for(int v:e[u]){ if(v==fa) continue; get_root(v,u); siz[u]+=siz[v]; maxp[u]=max(maxp[u],siz[v]); } maxp[u]=max(maxp[u],sum-siz[u]); //考虑删除u后父亲节点一侧子树的大小 root=(maxp[root]<maxp[u]?root:u); //更新重心 } ``` 调用这个函数前要记得将 `root` 初始化为 0，将 `maxp[0]` 初始化为正无穷，以及按照需要初始化 `sum`。 一般题目只需要求一个重心即可。如果有两个重心并且都要求出来也是同理，dfs 之后再遍历一下所有点就行。 ## 树的直径 ### 定义 树上最远两点的简单路径叫做树的直径。树的直径是不唯一的。也被称为树的最长链。 ### 求解 两遍 dfs 或树形 dp。 #### 两遍 dfs 任选一个节点 $s$ 作为树根，dfs 找到距离 $s$ 最远的点 $u$，再 dfs 一遍找到距离 $u$ 最远的点 $v$，$u$ 到 $v$ 就是树的一条直径。 证明一下。考虑我们只需要证**从树上任意一点出发，到其最远的一点一定是树的直径的一个端点**。可以使用反证法证明：\ 记出发点为 $s$，从 $s$ 出发遍历到最远的一个点为 $u$，树的一条直径为 $x$ 到 $y$，$u$ 不为 $x$ 或 $y$。分类讨论三种情况。 **情况 1** 若 $s$ 在 $\delta(x,y)$ 上。则有 $$\delta(s,u)>\delta(s,y)$$ 不等式两边同时加 $\delta(s,x)$，有 $$\delta(x,u)>\delta(x,y)$$ 与 $\delta(x,y)$ 是树上最长的简单路径不符； **情况 2** 若 $s$ 不在 $\delta(x,y)$ 上，且 $\delta(s,u)$ 与 $\delta(x,y)$ 有交。 $$\delta(s,u)>\delta(s,y)$$ 设两条路径相交部分一端为 $z$，不等式两边同时减 $\delta(s,z)$，有 $$\delta(z,u)>\delta(z,y)$$ 不等式两边再同时加 $\delta(x,z)$，有 $$\delta(x,u)>\delta(x,y)$$ 同样与原假设不符； **情况 3** 若 $s$ 不在 $\delta(x,y)$ 上，且 $\delta(s,u)$ 与 $\delta(x,y)$ 无交。 $$\delta(s,y)>\delta(s,x)$$ 设 $\delta(s,u)$ 上有一点 $z$，$\delta(x,y)$ 上有一点 $z'$。不等式两边同时减 $\delta(s,z)$，有 $$\delta(z,u)>\delta(z,y)$$ 不等式两边再同时减 $\delta(z,z')$，有 $$\delta(z',u)>\delta(z',y)$$ 不等式两边同时加 $\delta(x,z')$，有 $$\delta(x,u)>\delta(x,y)$$ 同样与原假设不符。 综上所述，三种情况都与原假设不符，原定理得证。 注意：上面的证明是建立在原树中无负权边的情况下，当有负权边时，原定理不一定成立。因此当树中有负权边时，无法使用两遍 dfs 求解树的直径。这时候就不得不使用树形 dp 了。 代码： ```cpp int d[N]; int maxx,ans,ans1; void dfs(int u,int fa){ //求解距离u最远的点到u的距离 for(int i=head[u];i;i=nxt[i]){ int vv=v[i]; if(vv==fa) continue; d[vv]=d[u]+w[i]; //d[v]记录u到v的距离 if(d[vv]>maxx) maxx=d[ans=vv]; //maxx记录最远距离，ans记录最远距离的点 dfs(vv,u); } } int main(){ //建图 dfs(1,0); maxx=d[ans1=ans]=0; //重新初始化，ans1记录直径的一端 dfs(ans,0); //此时求解完成，ans和ans1记录了直径的两端，maxx记录了距离 return 0; } ``` #### 树形 dp dfs，记录节点 $1$ 为树根时，每个节点作为其子树的根向下的最长链长度 $d_1$ 和次长链（与最长链无交）长度 $d_2$，直径的长度就是所有节点 $d_1+d_2$ 的最大值。也就是说，树的直径等于树的某个点子树中最长链与次长链的和。 相较于两遍 dfs，能够在有负权边时求解，但是不方便记录树的直径的两个端点（也就是不方便遍历树的直径上的节点）。 代码： ```cpp int d1[N],d2[N]; //分别记录最长链长度和次长链长度 int maxx; //记录树的直径长度 void dfs(int u,int fa){ for(int i=head[u];i;i=nxt[i]){ int vv=v[i]; if(vv==fa) continue; dfs(vv,u); //回溯时更新 if(d1[vv]+w[i]>d1[u]) d2[u]=d1[u],d1[u]=d1[vv]+w[i]; //比最长链和次长链都长 else if(d1[vv]+w[i]>d2[u]) d2[u]=d1[vv]+w[i]; //只比次长链长 } maxx=max(maxx,d1[u]+d2[u]); //求完一个点之后更新 } int main(){ //建图 dfs(1,0); //此时求解完成，maxx记录了距离 return 0; } ``` 也可以只记录树的最长链长度。每次更新最长链之前先更新直径长度即可。更多解释见代码注释。 ```cpp int d[N]; //记录最长链长度 int maxx; //记录树的直径长度 void dfs(int u,int fa){ for(int i=head[u];i;i=nxt[i]){ int vv=v[i]; if(vv==fa) continue; dfs(vv,u); //回溯时更新 maxx=max(maxx,d[u]+(d[vv]+w[i])); //d[u]和(d[vv]+w[i])一个是最长链长度，一个是次长链长度 d[u]=max(d[u],d[vv]+w[i]); } } int main(){ //建图 dfs(1,0); //此时求解完成，maxx记录了距离 return 0; } ``` ## 基环树 严格来说不是树，而是一种特殊的图。 定义：简单来说就是一棵树加上一条边。 通常思路是先找环，然后删环上边转换成树。 从找环开始。 dfs 找环： ```cpp bool vis[N]; vector<int> cir; //记录环上各个点 bool oncir[N]; //是否在环上 bool flag,flagg; //是否已经发现了环，环是否已经全部找完 int id; //第一个被遍历两次的点，也就是环上第一个被找到的点 void get_cir(int u,int fa){ //找环 vis[u]=1; for(int v:e[u]){ if(v==fa){fa=0;continue;} //fa=0是为了防止重边（二元环） if(vis[v]){ //第一次发现环上的一个节点（实际上这个点是环上第一个被遍历两次的点） flag=1; //标记已经发现了环 id=v; //记录环上的“起点” cir.push_back(v); //记录环 oncir[v]=1; return; //防止重复遍历 } get_cir(v,u); if(flagg) return; if(flag){ //回溯时，如果已经发现了环 cir.push_back(v); //记录环 oncir[v]=1; if(id==u){ //从环上绕回到了“起点” flagg=1; return; } return; } } } ``` 无向基环树还可以用并查集找环，很显然，不再赘述。 还可以用拓扑，拓扑排序完之后入度不为 1 的点在环上。 记一些套路。当然以下题目解法不唯一，仅作参考。这种题做多了就会了，看见新的随时更新吧。 - 找到环之后最基础的是枚举断边，然后当作树来跑，如 [P5022](https://www.luogu.com.cn/problem/P5022)。 - 有些题目断边没有影响，可以断边之后，断掉边的两边两个点分别为根跑一遍，然后取最优，如 [P1453](https://www.luogu.com.cn/problem/P1453)。 - 反悔的思想，因为环上可以由两个方向从一个点走到另一个点，如 [P5049](https://www.luogu.com.cn/problem/P5049)。 - 删去边有时是直接忽略即可，但有些需要单独考虑，跑两次，一次忽略正常边，另一次强制考虑删去边，如 [P10933](https://www.luogu.com.cn/problem/P10933)。 - 先跑环上各个点的子树，然后再从环上统计，这其中有一部分可以环上和子树上一块跑，如 [CF1454E](https://www.luogu.com.cn/problem/CF1454E)。 - 一些建图，如 [CF1270G](https://www.luogu.com.cn/problem/CF1270G)。 ## 虚树 很多时候用于树形 dp。 有的时候直接 dp 的复杂度比较高，一次是 $O(n)$ 的。如果有多次可能会炸。然后你会发现它有一些点是对答案没有影响的，无需考虑，我们只需要考虑树上的关键点。这让我们想到把这些点单独拎出来。但是如果只考虑这些点，可能会导致树的结构被破坏，以及某些信息丢失。所以我们同时把这些关键点的 lca 一块拎出来。因此对关键点按 dfs 序进行排序，然后两两相邻求 lca，之后连边。 实际上，将这些点单独拎出来，然后构造出来的这棵新树就是虚树。 虚树通常有两种构造方法。 ### 二次排序 + lca 连边 上面基本说完了。排序后关键点两两求 lca，一块加入一个中间数组 $a$ 中，然后对 $a$ 排序并去重，之后再枚举 $a$ 序列中相邻的两个点编号 $x,y$，求其 lca 并连接 $lca(x,y),y$ 即可。 一个小细节是可以把 $1$ 号节点先扔进虚树，作为根节点。实际上，在虚树里，只要保证祖先后代的关系没有改变，就可以随意添加节点，只不过加的太多建虚树就没啥意义了，起不到优化作用。 代码： ```cpp bool cmp(int x,int y){return dfn[x]<dfn[y];} int m,h[N]; int a[N],len; vector<int> e[N]; //存虚树 bool is_key[N]; //是否是关键点 void build(){ //建虚树 if(!is_key[1]) h[++m]=1; sort(h+1,h+1+m,cmp); for(int i=1;i<=m;i++){ a[++len]=h[i]; if(i!=m) a[++len]=lca(h[i],h[i+1]); } sort(a+1,a+1+len,cmp); len=unique(a+1,a+1+len)-a-1; for(int i=1;i<len;i++) e[lca(a[i],a[i+1])].push_back(a[i+1]); } ``` ### 单调栈实现 曾经是几乎唯一的做法。所以你现在看几年前的题解几乎全是这种写法。不过既不如第一种方法好理解，又不如第一种好写，所以现在反而写的人少了。优点是相比第一种方法，常数更小。 用单调栈维护虚树上目前最右边的一条链。栈中一个节点的父亲节点是其下面的节点，最底下的是根节点。 具体构建虚树的步骤如下： 1. 向栈中添加 $1$ 号节点作为虚树的根，方便后续操作。 2. 分情况讨论： - 若当前节点与栈顶元素的 lca 是栈顶元素，说明它们在同一条链上，直接入栈； - 若当前节点与栈顶元素的 lca 不是栈顶元素，说明它们不在一条链上。也就是说，当前这条链已经全部找完了，我们需要连边并换到下一条链上。我们首先求出当前点和栈顶元素的 lca，记为 $p$，接下来判断：若 $p$ 的 dfs 序等于次大节点（栈顶下面的第一个点），说明 $p$ 就是次大节点，直接将栈顶元素向 $p$（次大节点）连边，并将栈顶元素弹出栈；否则，若 $p$ 的 dfs 序大于次大节点，说明 $p$ 还没有入过栈，此时将栈顶元素向 $p$ 连边，弹出栈顶元素，将 $p$ 入栈。 如此重复，直到遍历完序列里全部的节点，最后把栈中的元素一一弹出并连边即可。 代码如下： ```cpp bool cmp(int x,int y){return dfn[x]<dfn[y];} int m,h[N]; vector<int> e[N]; //存虚树 bool is_key[N]; //是否是关键点 int stk[N],top; //栈 void build(){ //建虚树 sort(h+1,h+1+m,cmp); top=1; if(!is_key[1]) stk[top]=1; //1号点入栈 for(int i=1;i<=m;i++){ int p=lca(h[i],stk[top]); if(p!=stk[top]){ //不在同一条链上 while(dfn[p]<dfn[stk[top-1]]) e[stk[top-1]].push_back(stk[top--]); //加边，弹栈 e[p].push_back(stk[top--]); //连边并弹栈 if(dfn[p]>dfn[stk[top]]) //p未入过栈 stk[++top]=p; //让p进栈 } stk[++top]=h[i]; //进栈 } for(int i=1;i<top;i++) e[stk[i]].push_back(stk[i+1]); //最后剩下的加边 } ``` ## 点分治 通常用于处理在**无根树**上对路径静态统计的题目。 对于一颗树上的路径，设根节点为 $root$，则路径可以分为两类：经过根节点的和不经过根节点的。经过根节点的可以从根节点断开变成两条链，不经过的显然一定在某棵子树中，可以递归求解。 考虑怎么递归。如果你直接往下走复杂度会被卡到 $O(n^2)$。因此我们考虑重心。根据重心的性质，重心分成的各个子树的大小不超过原树大小的一半，因此这样可以做到 $O(n \log n)$。 递归各个子树： ```cpp void work(int u){ vis[u]=1; calc(u); //计算 for(int i=head[u];i;i=nxt[i]){ //对每棵子树递归求解 int vv=v[i]; if(vis[vv]) continue; f[root=0]=sum=siz[vv];get_root(vv,0); //求子树的重心 work(root); } } ``` `calc()` 函数需要根据题目需要修改。[模板题题解](https://www.luogu.com.cn/article/sasoi03s)