Nikkukun's Blog
0%

树算法总结

发表于 更新于 分类于

树是一类特殊的图，一棵树是拥有 \(n\) 个节点与 \(n-1\) 条边的无向联通图。树的性质很多，因此关于树的算法也不少。

## 树的直径

即树上最远的点对距离，可以用 DFS 或动态规划在 $\(\mathrm{O}(n)\) 的时间内处理。NOIP 内容，不细讲。

可以证明，每个点在树上的最远点一定是直径的两端。

###DFS

随意从树上一个点 DFS 找到距离最远的点 \(u\)，再从 \(u\) 开始 DFS 找到距离最远的点 \(v\)，则直径为 \(u\to v\)。

### 动态规划

对每个节点记录它能到达最深和次深的距离 \(dep_{i,0},dep_{i,1}\)。考察节点 \(u\) 的每个子树 \(v\)：

  • 若 \(dep_{v,0}>dep_{u,0}\)，则用 \(u\) 的最大值更新 \(u\) 的次大值，用 \(v\) 的最大值更新 \(u\) 的最大值；
  • 否则若 \(dep_{v,0}>dep_{u,1}\)，用 \(v\) 的最大值更新 \(u\) 的次大值；
  • 否则考察下一个节点

则直径为 \(max_{u\in V}\{dep_{u,0}+dep_{u,1}\}\)，初始状态为 \(dep_{u,0}=dep_{u,1}=0\)。

## 最近公共祖先

求最近公共祖先（Lowest Common Ancestor）也是有点水。

###RMQ

处理出树的欧拉序，则从 \(u\) 到 \(v\) 的欧拉序中必定经过 \(LCA(u,v)\)，且是唯一一个深度最小的节点。用 RMQ 可以 \[\mathrm {O}(n\log {n})$ 预处理，\](1)$ 回答。

### 并查集

这是离线做法，没写过。但是时间复杂度是 $\(\mathrm{O}(n)\) 的。

### 倍增

通过 $\(\mathrm{O}(n\log{n})\) 预处理每个节点 \(u\) 的 \(2^k\) 倍祖先 \(anc_{u,k}\)（\(0\) 倍祖先为父节点）。对于每次询问 \((u,v)\) 且假设 \(dep_u\leq dep_v\)：

  1. 当 \(dep_u<dep_v\) 时，找到最大的 \(k\) 使得 \(anc_{u,k}\not= v\)，并将 \(anc_{u,k}\) 赋给 \(u\)，直到 \(dep_u=dep_v\)；
  2. 当 \(anc_{u,0}\not=anc_{v,0}\) 时，找到最大的 \(k\) 使得 \(anc_{u,k}\not=anc_{v,k}\)，并将 \(anc_{u,k}\) 赋给 \(u\)，\(anc_{v,k}\) 赋给 \(v\)，直到 \(anc_{u,0}=anc_{v,0}\)；
  3. \(LCA(u,v)=anc_{u,0}\)。

单次询问时间复杂度 $\(\mathrm{O}(\log{n})\)。第二步前需要特判 \(u\) 是否已经等于 \(v\)。

### 树链剖分

大概什么时候会写树剖的总结。树剖的预处理复杂度为 \[\mathrm {O}(n)$，单次询问时间复杂度 \]()$，常数比倍增小。虽然树剖可以求 LCA，但这算是树剖的附属品。

类似倍增，每次移动所在重链的 \(top\) 深度较大的节点到 \(top\) 的父节点，直到 \(u=v\)。需要特判 \(u\) 和 \(v\) 在同一重链上的情况。

## 树的重心

即子树节点数最大值最小的节点。每次都从重心开始进行点分治保证了点分治的层数为 $\(\mathrm{O}(\log{n})\)。

两次 DFS（可能爆栈）或三次 BFS 即可解决。

## 树上不相交最长链

在树上选择两条链，使链和距离最大且没有公共边。

如果考虑反悔思想，则变得很容易。对第一次选择的链（直径）上的边权取反，则第二次若取到了相同的边相当于取消选择这条边。两次都取直径保证了距离和最大，而画个图可以发现两次的公共边等价于没有选择，且仍然是两条链。

感觉可以扩展到 \(k\) 条链的情况，但是看起来不一定有 \(k\) 条链（可以拆链成几段充数）。时间复杂度 $\(\mathrm{O}(kn)\)。

## 树链剖分

终于到重点了。树链剖分（Heavy-Light Decomposition）就是将树分成不超过 \(\log{n}\) 条不相交的重链的方法。将树剖分后，就可以愉快地在树上使用线段树维护路径了。

剖分可以维护点，也可以维护边。但是都需要维护六个信息：子树大小 \(siz\)、节点深度 \(dep\)、父节点 \(pa\)、重儿子编号 \(son\)、所在重链顶节点 \(top\)、节点在线段树对应编号 \(idx\)。前四个可以在第一次 DFS 内求出，后两个需要在第二次 DFS 内求出。如果采用 BFS 需要三次。

上面这些变量的含义和方法可以在这里找到，此处不做赘述。

以下代码是基于点的树剖，基于边的树剖只需要改动 \(idx\) 就可以实现。 ​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct HLDcp{
    SegTree t;	//略去线段树定义
    int dep[N],siz[N],pa[N],son[N],top[N],idx[N];
    int nIdx;

    void Build(){
        nIdx=dep[0]=siz[0]=son[0]=0;
        DFS1();DFS2();
        t.Init(idx);t.Build();
    }

    void DFS1(int u=1,int pa=0){
        dep[u]=dep[HLDcp::pa[u]=pa]+1;
        siz[u]=1;son[u]=0;
        for(int i=0;i<a[u].size();i++){
            int v=a[u][i];
            if(v==pa)continue;
            DFS1(v,u);
            if(siz[v]>siz[son[u]])son[u]=v;
            siz[u]+=siz[v];
        }
    }

    void DFS2(int u=1,int pa=0){
        idx[u]=++nIdx;top[u]=u;
        if(son[pa]==u)top[u]=top[pa];
        if(son[u])DFS2(son[u],u);
        for(int i=0;i<a[u].size();i++){
            int v=a[u][i];
            if(v==pa||v==son[u])continue;
            DFS2(v,u);
        }
    }
};
树剖相当于将树映射到某个线性序列上，使得树能使用线性序列的数据结构（如线段树）。树剖的查询过程需要经过不超过 \(\log{n}\)条边，因此如果写线段树，则单次时间复杂度为\[\mathrm {O}(\log^2 {n})$；如果写树套树则为 \](^3{n})\(；如果写带修改区间第 \)k\(大则为 \)\(\mathrm{O}(\log^4{n})\)。

## 树分治

树分治可以基于点，也可以基于边。基于点的点分治每次找重心保证了不超过 \(\log{n}\) 层，而边分治十分不稳定。

参考 09 年论文《分治算法在树的路径问题中的应用》漆子超。

（因为只看了点分治，就只谈点分治吧。）

### 点分治

感觉没有题目都不懂怎么往下讲

一般用来解决树上点对或路径有关的题目，且结果具有高效可合并性。

#### 树上点对统计

题意：给定 n 个节点的带权无向树，统计树上距离不小于 \(k\) 的点对数。\((n\leq 10^5)\)。

最入门的点分治题目。假设我们在某一次分治已经找到重心 \(u\)，并对其子树完成了分治。现在考虑怎么合并。

求树上距离我们能想到之前提过的动态规划方法。假设我们已经得到了所有点的深度，那只需要排序后两个指针一前一后扫一次就可以在 \[\mathrm {O}(n)$ 统计了。要得到所有子树的深度可以一次 DFS 获得，时间复杂度也是 \](n)$。

然而我们发现这个方法会把子树中满足条件的点对也计算到经过 \(u\) 节点的满足条件节点对数，那么从结果里减去每个子树满足的点对数就可以了。

### 边分治

哈？

### 链分治

哈？

## 题目

怎么还没讲完就到题目了

### 树型动态规划

####APIO2010 巡逻

添加一条边能让新出现的环总体减少一次经过次数，添加两条边能让两个环不重复的部分减少一次经过次数（重复的部分仍然需要经过两次），并且这个部分恰好是两条链。因此找树上不相交最长链，从总数减去即可。

#### 概率充电器

是个好题。重点有两个：

  • 化正为反
  • 化并为交

具体来说是指对每个节点 \(u\)，考察被父节点或子节点充电化为考察既不被父节点又不被子节点充电。因为概率中求交要比求并方便多了。虽然我想到了化正为反，但是我陷入了同时考虑节点自己点亮或被相邻节点点亮的复合情况，并且没有处理好节点间的关系。如果处理好了就不难想到树型 DP 的方程。当然规模太大，需要 BFS。

假设 \(f_u\) 为不被子树和自己充电的概率，\(g_u\) 为不被父亲充电的概率，\(P\) 为父亲不被 \(u\) 之外的点充电的概率，则：

\[ f_u=(1-p_u)\sum_{v\in son} [f_v+(1-f_v)(1-w_{u,v})] \\ P=g_{pa_{pa}}\cdot \frac {f_{pa}}{f_u+(1-f_u)(1-w_{u,pa})} \\ g_u=P+(1-P)(1-w_{u,pa}) \]

即两种情况：充电但连边不通，不充电。

### 树链剖分

####CTSC2008 网络管理

一开始的想法很 naive，就是树剖之后再线段树套 Treap 维护区间第 \(k\) 大。然后复杂度大得要命。估摸着二分答案 + 树剖 + 线段树查询 + 平衡树查询一共 $\(\mathrm{O}(n\log^4{n})\)，竟然也能过。

不过正解是只需要主席树。毕竟区间第 \(k\) 大可以很轻松用可持久化线段树维护（需要离散化），然后我们发现这就是一个带修改的可持久化线段树，用树状数组的方式维护 \(n\) 个可持久化线段树并统计就好了。其他做法同上。猜测复杂度二分答案 + 树剖 + 可持久化线段树查询 + 树状数组统计一共 \[\mathrm {O}(n\log^4 {n})$。然而并不是。按照 DFS 序的主席树套树状数组就是 \](n^2{n})$。

####BZOJ2819 Nim

Nim 游戏先手获胜 \(\Leftrightarrow\) 异或不为 \(0\)，然后就是树上异或查询了。异或满足交换率（三种位运算符单独考虑都满足结合率、交换率），然后可以线段树，然后可以树剖，然后.. 就被卡 $\(\mathrm{O}(q\log^2{n})\) 了。

可以不用树剖。树上的区间查询相当于欧拉序连续区间查询，每次更新 \(u\) 时只会对 \(u\) 的子树产生影响。因此每次查询 \((u,v)\) 时答案为 \(st_v\ \mathrm{xor}\ ed_u\)，每次更新 \(u\) 时更新 \([st_u,ed_u+1]\) 即可。然后复杂度就降到 $\(\mathrm{O}(q\log{n})\) 了。

因此我们得到启发：如果修改只影响子树或祖先，则可以考虑在 DFS 序上用树状数组维护。下一题就是如此。

####BZOJ4765 普通计算姬

（其实不是树剖）

每一次更新节点只会影响祖先节点，而每一次询问却是树上分散点集的和。我们先考虑询问单点的情况，则每一次更新就可以用 DFS 序 + 树状数组在 \[\mathrm {O}(\log {n})​$ 维护前缀和（树剖 \](^2 {n})​$）。然而还有区间询问，不如考虑分块。

维护一个块，统计一个节点及其父节点在块 \(i\) 的总数，则每次更新可以在 \[\mathrm {O}(\sqrt {n})$ 内完成。而对于不是完整块的查询可以直接用上面的方法单点查询。总时间复杂度 \](q(+))$。

因此我们再次得到启发：当单点维护代价高时，区间查询可以考虑用分块维护。

### 树分治

####SPOJ1825 Free Tour II

论文题。

点分治，维护到各个子树中不超过 \(i\) 个黑点 \((i\leq siz_v)\) 的最长路径。我们发现 \(i>siz_v\) 的时候答案不会改变，因此我们可以认为这个状态数就是 \(siz_v\)。

论文说合并可以用平衡树轻易实现，然而我没想到怎么维护。

合并的时候对子树大小排序，考察从当前子树 \(v\) 到之前子树经过 \(min(lim,siz_v)\) 个黑色节点的最长路径并合并。合并 \(k\) 个子树的时间复杂度为 \[\mathrm {O}(\sum_{i=1}^k min_{j=1}^i\{siz_j\})=$\mathrm {O}(\sum_{i=1}^k siz_i)=$\mathrm {O}(siz_u)$。因此每层分治时间复杂度为 \](n)\(，对不超过 \)n\(条边的排序时间为 \)\(\mathrm{O}(\log{n})\)，因此总时间复杂度为 $\(\mathrm{O}(n\log{n})\)。

## 总结

树具有许多性质，利用这些性质可以在树上进行动态规划、剖分和分治。

  • 若给出了一个序列，序列间的关系只与 \(a_{i}\) 和 \(a_{\lfloor i/2 \rfloor} 相关 \)，则这个序列的关系可以构成一棵二叉树。

  • 不相交最长链的反悔思想：反权边。这在网络流里也有体现。

  • 树的遍历通常采用 DFS，但数据过大时需要采用 BFS。树的特性保证了其在拓扑序下也可以合并结果。

  • 在一类合并子树的动态规划 / 树分治的过程中，如果时间复杂度和当前已合并的子树大小有关，可以按子树大小顺序合并。这在一些题目中可以降低、保证复杂度。

  • 如果修改只影响子树或祖先，则可以考虑在 DFS 序上用树状数组维护而不是树剖。当单点维护代价高时，区间查询可以考虑用分块维护。

  • 然后我就喵喵喵了 TAT