(dfs)序就是一棵树在(dfs)遍历时组成的节点序列.
它有这样一个特点:一棵子树的(dfs)序是一个区间.
下面是(dfs)序的基本代码:
void dfs(int u)//dfs序:u是根节点
{
in[u]=tot;
for(auto v:g[u])
{
tot++;
dfs(v);
}
out[u]=tot;
}
从树的根节点进行(dfs)，对于每个节点记录两个信息，一个是(dfs)进入该节点的时间戳 (in[id])，另一个是 (dfs) 离开该节点的时间戳(out[id])。
如果给你一颗树, 和每个节点的权值，那么(DFS)序多用于以下⑦个经典问题。
①. 对某个节点 (X) 权值加上一个数(W) , 查询某个子树(X)里所有点权的和.
由于(X) 的子树在 (DFS) 序中是连续的一段, 只需要维护一个(DFS) 序列,用树状数组实现:单点修改和区间查询.
②. 对节点 (X) 到 (Y) 的最短路上所有点权都加一个数 (W) , 查询某个点的权值.
这个操作等价于
(a). 对(X) 到根节点路径上所有点权加 (W).
(b.) 对 (Y) 到根节点路径上所有点权加 (W).
(c.) 对 (LCA(x, y)) 到根节点路径上所有点权值减 (W).
(d.) 对 (LCA(x,y)) 的父节点 (fa(LCA(x, y))) 到根节点路径上所有权值减(W).
于是要进行四次这样从一个点到根节点的区间修改.将问题进一步简化, 进行一个点(X)到根节点的区间修改, 查询其他一点(Y)时,只有(X)在(Y)的子树内,(X)对(Y)的值才有贡献且贡献值为(W).
当单点更新 (X) 时, (X) 实现了对(X)到根的路径上所有点贡献了(W).于是只需要更新四个点(单点更新) ,查询一个点的子树内所有点权的和(区间求和)即可.
③. 对节点 (X) 到 (Y) 的最短路上所有点权都加一个数 (W,) 查询某个点子树的权值之和.
同问题②中的修改方法, 转化为修改某点到根节点的权值加/减 (W)
当修改某个节点(A), 查询另一节点 (B) 时
只有(A)在(B)的子树内, (Y)的值会增加
(W * (dep[A] - dep[B] + 1) => W * (dep [A] + 1) - W * dep[B]).
那么我们处理两个数组就可以实现:
处理出数组(Sum1),每次更新 (W*(dep[A]+1)) ,和数组 (Sum2),每次更新 (W).
每次查询结果为 (Sum1(R[B]) – Sum1(L[B]-1) - (Sum2(R[B]) – Sum2(L[B]-1)) * dep [B]) .
④. 对某个点 (X) 权值加上一个数 (W) , 查询 (X) 到 (Y) 路径上所有点权之和.
求 (X) 到 (Y) 路径上所有的点权之和, 和前面 (X) 到 (Y) 路径上所有点权加一个数相似
这个问题转化为:
(X) 到根节点的和 (+ Y)到根节点的和 (- LCA(x, y)) 到根节点的和 (- fa(LCA(x,y))) 到根节点的和
更新某个点 (x) 的权值时,只会对它的子树产生影响,对(x)的子树的每个点到根的距离都加了(W).
那么我们用”刷漆”(差分前缀和),更新一个子树的权值.给(L[x])加上(W),给(R[x]+1)减去(W),那么(sum(1~L[k])) 就是 (k) 到根的路径点权和.
⑤. 对节点(X)的子树所有节点加上一个值(W), 查询(X)到(Y)的路径上所有点的权值和
同问题④把路径上求和转化为四个点到根节点的和
(X)到根节点的和 (+ Y) 到根节点的和 (- LCA(x, y)) 到根节点的和 (- parent(LCA(x,y))) 到根节点的
再用刷漆只更新子树.
修改一点(A), 查询某点B到根节点时, 只有(B)在(A)的子树内, (A)对(B)才有贡献.
贡献为 (W * (dep[B] - dep[A] + 1) => W * (1 - dep[A]) + W * dep[B]).
和第三题一样, 用两个(sum1,sum2) 维护 (W *(dep[A] + 1)) ,和 (W).
最后答案就是 (sum2*dep[B]-sum1).
⑥. 对子树 (X) 里所有节点加上一个值 (W) , 查询某个点的值.
对(DFS)序来说, 子树内所有节点加(W), 就是一段区间加(W).
所以这个问题就是 区间修改, 单点查询.树状数组 + 刷漆(差分前缀和).
⑦.对子树X里所有节点加上一个值(W), 查询某个子树的权值和.
子树所有节点加(W), 就是某段区间加(W), 查询某个子树的权值和, 就是查询某段区间的和.
区间修改区间求和,用线段树可以很好解决.