1. 定义及理解:
dfs 序是深度优先遍历一颗树的时候产生的时间戳序列, 可以将树形结构有序地转化为线性结构, 从而将树上问题转化为线性问题
这时, 我们就可以用许多优秀的数据结构, 比如维护区间的线段树, 树状数组等方便地处理树上问题啦!
2. 重要的性质
(1)设 in[x]表示第一次 dfs 到 x 节点的时间戳, out[x]表示从 x 节点退出的时候的时间戳, num[time]表示 time 的时间戳所对应的
树上节点是哪一个. 其中, num 数组是我们新得到的 dfs 序列, 是一段线性节点序.
显然, 一颗以 x 节点为根的子树在 dfs 序中必然占据一段连续的区间[in[x],out[x]], 而这段区间内的所有节点是这颗子树的所有子节点.
- Code:
- void Dfs(int u,int fa)
- {
- in[u]=++cnt;// 记录进入 x 的时间戳
- dfs[cnt]=u;// 更新 dfs 序
- int v;//
- for(int i=head[u];i;i=e[i].next)
- {
- v=e[i].to;
- if(v!=fa)
- Dfs(v,u);// 搜索子树
- }
- out[u]=++cnt;// 记录离开 x 的时间戳
- dfs[cnt]=u;// 更新 dfs 序
- }
(2)问题一: 单点修改, 子树和查询:
求出整棵树的 dfs 序, 直接单点修改节点 x 对应在 dfs 序上的值, 然后子树和也就是求区间和, 考虑用树状数组或线段树维护即可!
问题二: 树链修改, 单点查询:
修改 (u,v) 节点间的值, 比如全部加上 a
那么我们考虑对四条链进行操作!
考虑 u--->root,v--->root,LCA(u,v)--->root,fa(LCA(uv))--->root!
我们将前两条路径上的所有点加 a, 后两条路径的所有点减去 a
可以用树状数组维护这个 dfs 序, 序列上依次对应每个 dfs 序上对应节点的权值!
然后修改? 这个树状数组其实维护的是 dfs 序的权值前缀和!
get_sum(x) 表示 1-x 的差分前缀和
- add(l[u],a),add(l[v],a),add(LCA(u,v),-a),add(fa(LCA(u,v)),-a);
- val(x)=get_sum(r[x])-get_sum(l[x]-1);
问题三: 子树整体修改, 查询单点到根节点的权值和, 以及单点的权值
比如我们对于以 x 节点为根的子树整体加 a
我们对于所有节点, 维护两个值
一个是 tag, 另一个是节点的自身权值;
我们提供两种操作:
1)直接进行单点修改
2)将以 x 为根的子树整体加 a
操作 1, 直接单点修改即可 操作 2, 对于所有点, tag+=a, 然后节点自身的权值, 增加一个 -(dep[x]-1)*a; 这个是为了抵消不在这个以 x 为根
的子树内的节点的贡献! 询问节点 y 到根的权值和的时候, 我们返回: tag*dep[y]+val[y];
然后操作即可!
例题: POJ3321 https://www.cnblogs.com/shenben/p/5764932.html
洛谷: P3178 树上操作
来源: http://www.bubuko.com/infodetail-3282261.html