树形结构转线性结构的方法 (帖子汇总)

发表于 8月 31日, 2011 分类于 essay

在图论中经常遇到一些很常见的问题，比如一个非常简单的例子，给你一棵树，每一个点都有一个权值，现在动态更新一个点的权值，叫你查询一个点对路径上所有点权的和，这种问题和图论的 Tree Problem 非常类似，我们可以利用树形结构转线性结构的方法来处理，我们考虑随便取一个点，比如说 $1$ ，作为根，这样我们就可以得到一个 DFS 序列，注意我们维护一个长度为 $2 \times N$ 的 DFS 序列，每次访问开始的时候，向序列中加入一个等于当前点权的元素，每次结束这个结点访问的时候，我们加入一个等于当前点权相反数的元素，举一个很简单的例子。

我们考虑边的序列是这样
3
1 2
1 3
点权是
5 7 10
那么我们得到的序列有可能是
5 7 -7 10 -10 -5

注意一个非常好的性质，我们记录访问开始的时候加入的元素的下标，那么我们可以非常快的利用前缀和来计算出根到一个点的路径上点权和是多少，还是上面的例子，点权和的答案是

1 2	2 : [5 7] -7 10 -10 -5 = 12 3 : [5 7 -7 10] -10 -5 = 15

这样，我们可以维护一个线段树或者树状数组，对于更改点权的操作，假设我要把一个结点点权改成 v，我们在开始访问对应的下标处，把元素值改成 $v$ ，在其结束访问对应的下标处把元素改成 $-v$ ，这样还是保证了括号序列的匹配性。

对于查询操作，假设我要求 $u$ 和 $v$ 路径上全部结点的权值之和，我们可以求出 $u$ 和 $v$ 的 LCA，我们记录为 $t$ ，那么我们可以求出根到 $u$ 、 $v$ 和 $t$ 的权值之和，答案就是 $\sum{u}+\sum{v}-2 \times \sum{t}+w_t$ ，注意不要忘了加上那个 $t$ 的权值。

此外，Tree Problem 也是一个很经典的问题，对于 Tree Problem，我们可以只记录入点，不记录出点，但是要记录每一个点的管辖范围，注意一个点的子树在 DFS 序列中一定是连续的，那么我们就可以记录下这个点的管辖范围，然后利用树状数组维护这个序列，区间查询就可以了，至于需要查找大于其标号的点的个数，做法大家应该是都知道了的，还不是很清楚的同学可以自己再想想。

类似的问题有 POJ 的一题，叫做 Apple Tree，可以去做做。

树形结构转线性结构在关于树的统计问题中还有非常多的运用，暑假的时候，大家如果有兴趣，可以去看看，做法很巧妙，代码量不大，是此类问题的共同性质。

所谓的括号序列，就是将一个树形结构转化为线性结构，然后通过线性结构间接地对结点和路径的更新和查询操作。

好，现在步入正题，首先我们考虑一个很经典的问题，HDU3966，也就是昨天 HIT 的 F 题的模型：

大致题意

给你一棵树，现在有两种操作，一个是修改 u 到 v 路径上点的权值 (全部增加一个值)，另外一个是查询一个点的点权。

对于此类的问题，我们可以这么考虑，先将树形结构转化为线性结构，举下面的一个例子。

我们可以通过 DFS 得到它的一个括号序列

1 2 3 -3 -2 4 -4 5 -5 -1
其中
l[1] = 1 r[1] = 10
l[2] = 2 r[2] = 5
l[3] = 3 r[3] = 4
l[4] = 6 r[4] = 7
l[5] = 8 r[5] = 9

我们现在要做的是更新区间查找点，利用树状数组维护括号序列的增量 (注意这里是增量，初始化全部为 $0$ )，我们这么考虑，对于每一个更新操作，假设更新的是 $u$ 到 $v$ 路径上的点权全部加 $w$ ，那么对于 $u$ ，我们做的是将 $1$ 到 $l_u$ 位置上的元素全部加 $w$ ，对于 $v$ 我们做类似的处理。

你会发现，更新 $1$ 到 $l_u$ 上的元素值的时候，对于一个结点 $x$ ，如果 $x$ 是 $u$ 的祖先，那么 $x$ 一定是左括号被增加了 $w$ ，如果 $x$ 不是其祖先，比如说 $u$ 为 $4$ 的时候， $3$ 不是 $4$ 的祖先，那么 $x$ 一定是左右括号都被增加了 $w$ 。通过这个例子，大家应该都知道怎么做了吧，对于每次更新，我们将 $1$ 到 $l_u$ 以及 $1$ 到 $l_v$ 元素全部加 $w$ ，然后将 $u$ 和 $v$ 的 LCA 的左括号的位置找出来，假设为 $l$ ，那么 $1$ 到 $l-1$ 的全部元素减去 $2w$ ，因为我们要更新的是路径上的值，这时候我们会发现 LCA 会被更新了两次，所以 LCA 对应的左括号位置元素减 $w$ ，这样我们就完成了一次更新操作。

对于查询操作，看了上面一段话，应该会知道怎么做了，一个点的点权增加量就是等于其左括号的增加量减去右括号的增加量，这样我们就可以利用一个树状数组配合在线 LCA 在 $O(N \lg N)$ 的时间内得到所有的查询的答案。

第二个例子是一个高级数据结构的题，不过是非常经典的一题了，题号是 HDU2475，题目抽象后的大意是这样的：

大致题意

给你 N 棵树，我们有两个操作，一个是将一棵树的根结点接到另外一棵树的某一个结点下面，另外一个操作是查询一个结点所在的树的根。

对于这个问题，我们这么考虑，首先我们可以将全部的树逐个 DFS，这样对于每一棵树都可以得到一个括号序列，对于连结操作，我们将那个根所在的左右括号的一整段取出，连接到新的结点的左括号右边，这么做我们可以保证得到的一定也是一个括号序列。另外一个是查询操作，我们直接去找其结点所在的括号序列靠最左边的是谁就可以了。

对于这个问题，我们用 splay 来维护这些括号序列，我们为每一个结点分配一个左括号和右括号的结点，然后做序列即可，注意查询的细节。

利用 splay 来维护括号序列，对于一个 DFS 序列，我们入栈记录一次，出栈记录一次，我们用 x 表示 x 这个结点入栈的点，用 $x+n$ 表示 $x$ 出栈的点，那么对于这个问题可以轻松转化过来。

对于 MOVE 操作，如果可以移动，我们进行 cut 操作和 add 操作。
对于 cut 操作，我们将 $x$ 和 $x+n$ 分别旋根，这样我们可以得到一个 $x$ 和 $x+n$ ， $x+n$ 是根， $x$ 是其左子树的某一个结点，这样 $x$ 的左子树和 $x+n$ 的右子树是无效的，我们剪掉它们，并且将 $x+n$ 的右子树接到 x 的左子树最后，接着把 $x+n$ 旋根，保证平衡性。
对于 add 操作，我们将新的父亲结点旋到根， $x+n$ 旋到根，然后进行连接，注意新的父亲结点的右子树，需要接到 $x+n$ 的右子树上去。
对于初始化，我们可以确定每一个结点的父亲结点，然后逐个进行 add 就是。

最后的问题就是如何判断 $y$ 是不是 $x$ 的子树，这个的判断方法是先对 $x$ 执行 cut 操作，注意这时候两个子树不要合并，然后再去查询 y 的根结点，如果 $y$ 的根结点是 $x$ ，说明 $y$ 是 $x$ 的子树，最后记得复原。复原的时候要把 $x$ 和 $x+n$ 旋根，两个子树旋根，然后拼接。

查询一个结点的根结点，其实就是 DFS 序列的起点，也就是所在树的最小元素，将 $x$ 旋根，找左子树的最小值即可。

注意这题不能用找祖先结点的方法来确定两个树的关系，因为有可能他们同是一颗树的两棵不同子树，这样找会有问题。

最后一题可以算是第一题的变形吧，不过没发现哪个 OJ 有此类的题，具体题意如下：

大致题意

给你一棵树，每次可以对 $u$ 到 $v$ 路径上的全部点的点权加 $w$ ，可以查询 $u$ 到 $v$ 的点权之和。

我们可以这么考虑，对于 A 题，我们记录的是每一个点的增量，这题我们还可以记录到一个位置前缀和的增量，从它到最后的后缀和的增量，这样查询 $u$ 到 $v$ 的权值之和，就是查询根到 $u$ 的权值的增量加上根到 $v$ 的权值的增量，减去根到 LCA 的增量，加上 LCA 的增量，注意后缀和用来计算右括号的增量，那么根到 $u$ 的权值增量和就是 $1$ 到 $l_u$ 的前缀增量和减去 $r_u$ 到 $2 \times N$ 的后缀增量和，这样可以利用一个线段树来维护这三个值，在 $O(N \lg N)$ 的时间内得到解。

其实这个系列还有很多相似的问题的，但是都可以转化为这个类型上去，所以就不在过多的举例了，在最后主要提一下关于边权的问题，其实边权可以把他们转化为点权来做，还是举几个例子。

第一个例子很简单，给你一棵树，现在有两种操作，一种是一个边的权值加 $v$ ，另一个是查询两个点的距离，这个问题我们可以这么考虑，用点权代替边权，DFS 得到父亲结点和孩子结点的关系之后，我们用一个点的权值来代替连进这个点的边权的权值，这样就可以转化为括号序列的问题了。

第二个例子，是给你一棵树，每次可以更新一个边的边权，保证边权是正的，求任意点到根的距离的最大值，我们可以这么考虑，直接利用第一个例子的结论，记录前缀和的最大值即可，然后我们就可以在 $O(N \lg N)$ 的时间内来维护这个性质。

总之，边权的问题我们可以用点权来代替，如果遇到一些恶心的题目，既有边权又有点权的，我们可以考虑用多棵线段树或者树状数组来维护边权和点权，这样我们就可以在 $O(N \lg N)$ 的时间内完成相应的更新、查询操作。