dfs 序七个经典问题

Mason123456 · 2024-08-12 21:15:08 · 算法·理论

转载——dfs 序七个经典问题

查询：sum_{out_u} - sum_{in_u - 1}

用树状数组或线段树即可。

树链修改，子树和查询

树链修改部分同上一问题。下面考虑子树和查询问题：前一问是从贡献的角度，子树和同理。

对于节点 v 其到根节点的权值和，考虑其子节点 u 的贡献：w_u \times (dep_u - dep_v + 1) = w_u \times(dep_u + 1) - w_u \times dep_v

所以节点 v 的子树和为：

所以用两个树状数组或线段树即可。

第一个维护 \sum w_i\times(dep_i+1)

第二个维护 \sum w_i

单点更新，树链和查询

官方做法

树链和查询与树链修改类似，树链和 u, v 等于下面四个部分和相加：

3. \text{lca} \to root$ 上所有点权和 $\times -1
4. fa(\text{lca}) \to root$ 上所有点权和 $\times -1

所以问题转化为：查询点 u \to root 上所有点权和。

修改节点 u 权值，当且仅当 v 是 u 的子孙节点时，u 对 v 的值有贡献。

差分前缀和，v 的权值 = dfs 中，[1, in_v] 的区间和。

单点修改：in_u + w, ~ out_u + 1 - w

欧拉序做法

同官方做法，将 u, v 链分成 4 个部分，使用欧拉序存 dfs 序，即出入都花时间。

单点修改 u 时，将 in_u + w, ~ out_u - w，这样可以做到，任意节点 v \to root 上，旁边的子树和都已经与自己抵消，所以 \text{dfn} \to sum[root, in_v] 即为答案。

子树修改，单点查询

修改节点 u 的子树权值，在 dfs 序上就是区间修改，单点权值查询就是单点查询。

区间修改，单点查询问题，用树状数组或线段树即可。

子树修改，子树和查询

用树状数组或线段树即可。

子树修改，树链查询

树链查询同上，等价为根节点到 v 节点的链上所有节点和问题。

修改节点 u 的子树权值，当且仅当 v 是 u 的子孙节点时（或 u = v），u 对 v 的值有贡献。