\(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\), 查询某个子树的权值和, 就是查询某段区间的和.
区间修改区间求和,用线段树可以很好解决.