换根 DP
大约 5 分钟
换根 DP
- OI Wiki: https://oi-wiki.org/dp/tree/
| 题目 | 难度 | |
|---|---|---|
| 834. 树中距离之和 | 困难 | |
| 2581. 统计可能的树根数目 | 困难 | |
| 2858. 可以到达每一个节点的最少边反转次数 | 困难 | |
| 310. 最小高度树 | 中等 | |
| 3241. 标记所有节点需要的时间 | 困难 | 第二类换根 DP |
换根 DP / 二次扫描法（from 灵神）
// 换根 DP / 二次扫描法
// 【图解】一张图秒懂换根 DP！（Python/Java/C++/Go/JS）https://leetcode.cn/problems/sum-of-distances-in-tree/solution/tu-jie-yi-zhang-tu-miao-dong-huan-gen-dp-6bgb/
// https://codeforces.com/blog/entry/20935
// https://ei1333.hateblo.jp/entry/2017/04/10/224413
//
// todo 题集 https://atcoder-tags.herokuapp.com/tags/Dynamic-Programming/Every-Direction-DP
//
// LC310 也可以用拓扑排序的思想 https://leetcode.cn/problems/minimum-height-trees/
// - https://codeforces.com/problemset/problem/1881/F
// LC834 https://leetcode.cn/problems/sum-of-distances-in-tree
// https://codeforces.com/problemset/problem/763/A 1600（有更巧妙的做法）
// https://codeforces.com/problemset/problem/219/D 1700
// - LC2858 https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/
// - LC2581 https://leetcode.cn/problems/count-number-of-possible-root-nodes/
// https://codeforces.com/problemset/problem/1822/F 1700
// https://codeforces.com/problemset/problem/1324/F 1800 类似最大子数组和
// https://codeforces.com/problemset/problem/109/C 1900 也有组合数学做法
// https://codeforces.com/problemset/problem/1092/F 1900
// https://codeforces.com/problemset/problem/1882/D 1900
// https://codeforces.com/problemset/problem/337/D 2000
// https://codeforces.com/problemset/problem/791/D 2100
// https://codeforces.com/problemset/problem/1187/E 2100
// https://codeforces.com/problemset/problem/543/D 2300 注意不存在逆元的情形
// https://codeforces.com/problemset/problem/1626/E 2400
// https://codeforces.com/problemset/problem/1794/E 2400
// https://codeforces.com/problemset/problem/1691/F 2500 计数
// https://codeforces.com/problemset/problem/1320/E 3000 虚树
// https://atcoder.jp/contests/dp/tasks/dp_v
// https://atcoder.jp/contests/abc222/tasks/abc222_f 还可以用直径做
// todo https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_m
// https://atcoder.jp/contests/abc337/tasks/abc337_g
// https://www.luogu.com.cn/problem/P3047 对于每个点 v，计算到点 v 距离为 k 的点权和（k 是定值）
// https://www.luogu.com.cn/problem/P3478
// https://www.luogu.com.cn/problem/P2986
// https://ac.nowcoder.com/acm/contest/59717/F
// 换根 DP · 其一（简单情况）
// 第一次 DFS 算出以 0 为根的答案 ans0（一般是自底向上）
// 第二次 DFS 基于 ans0，算出从节点 x 换到子节点 y 的答案的「变化量」，从而计算出其它节点的答案（一般是自顶向下）
//
// 每个点到其余点的距离之和 LC834 https://leetcode.cn/problems/sum-of-distances-in-tree
// - 【图解】一张图秒懂换根 DP！https://leetcode.cn/problems/sum-of-distances-in-tree/solution/tu-jie-yi-zhang-tu-miao-dong-huan-gen-dp-6bgb/
// - 变形：把距离之和改成每个距离的平方之和、立方之和
// - 记录子树大小 size[v] 和子树每个节点的深度之和 sum(dep[sub])
// https://atcoder.jp/contests/abc220/tasks/abc220_f
// https://codeforces.com/problemset/problem/1324/F 1800 类似最大子数组和
// https://codeforces.com/problemset/problem/109/C 1900 也有组合数学做法
// https://codeforces.com/problemset/problem/791/D 2100 任意两点距离除以 k 的上取整之和
// https://atcoder.jp/contests/abc160/tasks/abc160_f 2048=CF2260
reroot1 := func(g [][]int) []int {
ans := make([]int, len(g))
size := make([]int, len(g))
var dfs func(int, int, int)
dfs = func(x, fa, depth int) {
ans[0] += depth //
size[x] = 1
for _, y := range g[x] {
if y != fa {
dfs(y, x, depth+1)
// ans[0] += ...
size[x] += size[y]
}
}
}
dfs(0, -1, 0)
var reroot func(int, int)
reroot = func(x, fa int) {
for _, y := range g[x] {
if y != fa {
ans[y] = ans[x] + len(g) - size[y]*2 //
reroot(y, x)
}
}
}
reroot(0, -1)
return ans
}
// 换根 DP · 其二（维护最大次大）
// LC3241 https://leetcode.cn/problems/time-taken-to-mark-all-nodes/
// https://codeforces.com/problemset/problem/1822/F 1700
// https://codeforces.com/problemset/problem/633/F 2600 计算最大次大第三大（也可以直接树形 DP，无需换根）
reroot2 := func(g [][]struct{ to, wt int }) []int {
nodes := make([]struct{ fi, se, fiW int }, len(g))
var dfs func(int, int) int
dfs = func(v, fa int) int {
p := &nodes[v]
for _, e := range g[v] {
w := e.to
if w == fa {
continue
}
d := dfs(w, v) + e.wt // 从 v 出发，往 w 方向的最大链和
if d > p.fi {
p.se = p.fi
p.fi = d
p.fiW = w
} else if d > p.se {
p.se = d
}
}
return p.fi
}
dfs(0, -1)
ans := make([]int, len(g))
var reroot func(int, int, int)
reroot = func(v, fa, fromUp int) {
p := nodes[v]
ans[v] = max(fromUp, p.fi) // 从 v 出发的最大链和
for _, e := range g[v] {
w := e.to
if w == fa {
continue
}
exceptW := p.fi
if w == p.fiW {
exceptW = p.se // 对于 w 来说，上面要选次大的
}
reroot(w, v, max(fromUp, exceptW)+e.wt)
}
}
reroot(0, -1, 0)
return ans
}
// 换根 DP · 其三（前后缀分解写法，适用性最广）
// 使用时根据题目修改 data unit moveEdge merge
// https://nyaannyaan.github.io/library/tree/rerooting.hpp.html
// https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
// https://atcoder.jp/contests/dp/tasks/dp_v 母题
// https://codeforces.com/contest/1822/problem/F 1700
// https://codeforces.com/problemset/problem/543/D 2300
// https://atcoder.jp/contests/abc160/tasks/abc160_f
// https://atcoder.jp/contests/abc222/tasks/abc222_f
rerootPreSuf := func(g [][]int, root int) {
// type data struct{ x, y int }
type data int
const unit data = 0
// 返回 d 在通过 v-w 边之后的结果 *也可以传入边权
// swap=true 表示 v-w 是换根时的那条边
moveEdge := func(d data, v, w int, swap bool) data {
return d + 1 // add weight from v to w
}
// 返回 p 和 q 合并后的结果（p 和 q 已经包含边的信息）
merge := func(p, q data) data {
return max(p, q) // p + q
}
// 以 root 为根时的子树信息
subData := make([]data, len(g))
var dfs func(int, int)
dfs = func(v, fa int) {
res := unit
for _, w := range g[v] {
if w == fa {
continue
}
dfs(w, v)
res = merge(res, moveEdge(subData[w], v, w, false)) // v-w 边
}
subData[v] = res
}
dfs(root, -1)
ansAtRoot := make([]data, len(g))
var reroot func(int, int, data)
reroot = func(v, fa int, movedFaData data) {
// 必要时特判 fa < 0 的情况
ansAtRoot[v] = merge(movedFaData, subData[v])
// suf 是 g[v] 的子树后缀汇总信息（已经包含 v-g[v][i] 边）
ngv := len(g[v])
suf := make([]data, ngv+1)
suf[ngv] = unit
for i := ngv - 1; i >= 0; i-- {
w := g[v][i]
if w != fa {
suf[i] = merge(suf[i+1], moveEdge(subData[w], v, w, false)) // v-w 边
} else {
suf[i] = suf[i+1]
}
}
// pre 是 g[v] 子树前缀汇总信息（已经包含 v-g[v][i] 边）
pre := unit
for i, w := range g[v] {
if w == fa {
continue
}
// mergedData 是除了 subData[w] 以外的子树汇总信息（已经包含 v-g[v][i] 边）
mergedData := merge(movedFaData, merge(pre, suf[i+1]))
reroot(w, v, moveEdge(mergedData, w, v, true)) // w-v 边（以 w 为根）
pre = merge(pre, moveEdge(subData[w], v, w, false)) // v-w 边
}
}
reroot(root, -1, unit)
for _, res := range ansAtRoot {
_ = res
// ...
}
}（全文完）