共计 3096 个字符，预计需要花费 8 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 834. 树中距离之和 ，难度为 艰难。
Tag :「树形 DP」、「DFS」、「动静布局」、「树」
给定一个无向、连通的树。
树中有 n 个标记为 0...n-1 的节点以及 n-1 条边。
给定整数 n 和数组 edges，$edges[i] = [a_{i}, b_{i}]$ 示意树中的节点 $a_{i}$ 和 $b_{i}$ 之间有一条边。
返回长度为 n 的数组 answer，其中 answer[i] 是树中第 i 个节点与所有其余节点之间的间隔之和。
示例 1:
输出: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输入: [8,12,6,10,10,10]
解释: 树如图所示。咱们能够计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
也就是 1 + 1 + 2 + 2 + 2 = 8。因而，answer[0] = 8，以此类推。示例 2:
输出: n = 1, edges = []
输入: [0]示例 3:
输出: n = 2, edges = [[1,0]]
输入: [1,1]提醒:
- $1 <= n <= 3 \times 10^4$
- $edges.length = n – 1$
- $edges[i].length = 2$
- $0 <= a_{i}, b_{i} < n$
- $a_{i} != b_{i}$
- 给定的输出保障为无效的树
树形 DP
对于树形 DP，能够轻易以某个节点为根，把整棵树“拎起来”进行剖析，通常还会以“方向”作为切入点进行思考。
无妨以编号为 0 的节点作为根节点进行剖析：假如以后解决到的节点为 u，以后节点 u 的父节点为 fa，同时 u 有若干子节点 j。
对于任意节点 u 而言，其树中距离之和可依据「方向 / 地位」分为两大类（对应示例图的左右两局部）：
- 所有从节点
u“往下”延长所达的节点间隔之和，即所有通过u -> j边所能拜访到的节点间隔之和 - 所有从节点
u“往上”延长所达的节点间隔之和，即通过u -> fa边所能拜访到的节点间隔之和
假如咱们可能用 $f[u]$ 和 $g[u]$ 预处理出每个节点“往下”和“往上”的间隔之和，那么就有 $ans[u] = f[u] + g[u]$。
不失一般性别离思考 $f[u]$ 和 $g[u]$ 该如何计算。
为了不便，起始先用「链式前向星」对 edges 进行转存，同时在递归计算 $f[u]$ 时，将父节点 fa 也进行传递，从而防止遍历节点 u 的出边时，从新走回 fa。
$f[u]$ 的推导
对于叶子节点（没有“往下”出边的节点），咱们有 $f[u] = 0$ 的人造条件，计算好的叶子节点值可用于更新其父节点，因而 求解 $f[u]$ 是一个「从下往上」的递推过程。
假如以后解决到的节点是 u，往下节点有 $j_{1}$、$j_{2}$ 和 $j_{3}$，且所有 $f[j]$ 均已计算实现。
因为 $f[u]$ 是由所有存在“往下”出边的节点 j 奉献而来。而单个子节点 j 来说，其对 $f[u]$ 的奉献该当是：在所有原有节点到节点 j 的间隔门路中，额定减少一条以后出边（u -> j），再加上 1（代表节点 u 到节点 j 的间隔）。
原门路间隔之和恰好是 $f[j]$，额定须要减少的出边数量为原来参加计算 $f[j]$ 的点的数量（即挂载在节点 j 下的数量），因而咱们还须要一个 c 数组，来记录某个节点下的子节点数量。
最终的 $f[u]$ 为所有符合条件的节点的 j 的 $f[j] + c[j] + 1$ 的总和。
$g[u]$ 的推导
对于树形 DP 题目，“往下”的计算往往是容易的，而“往上”的计算则是稍稍麻烦。
假如以后咱们解决到节点为 u，将要遍历的节点为 j，思考如何应用曾经计算好的 $f[X]$ 来求解 $g[j]$。
这里为什么是求解 $g[j]$，而不是 $g[u]$ 呢？
因为咱们求解的方向是“往上”的局部，必然是用父节点的计算结果，来推导子节点的后果，即 求解 $g[u]$ 是一个「从上往下」的过程。
对于树形 DP，通常须要对“往上”进一步拆分：「往上再往上」和「往上再往下」：
-
往上再往上：是指通过了
j -> u后，还必然通过u -> fa这条边时，所能达到的节点间隔之和：这部分对 $g[j]$ 的奉献为：在所有原有节点到节点
u的间隔门路中，额定减少一条以后出边（u -> j），减少以后出边的数量与节点数量雷同，点数量为 $n – 1 – c[u]$，含意为 总节点数量 减去u节点以及子节点数量。即此局部对 $g[j]$ 的奉献为 $g[u] + n – 1 – c[u]$。
-
往上再往下：是指通过了
j -> u后，还通过「除u -> j以外」的其余“往下”边时，所能达到的节点间隔之和：这部分的计算须要先在 $f[u]$ 中剔除 $f[j]$ 的奉献，而后再加上额定边（
u -> j）的累加数量，同样也是节点数量。从 $f[u]$ 中剔除 $f[j]$ 后为 $f[u] – f[j] – c[j]$，而点的数量为 $c[u] – 1 – c[j]$，含意为在以节点
u为根的子树中剔除调用以节点j为根节点的局部。即此局部对 $g[j]$ 的奉献为 $f[u] – f[j] – c[j] + c[u] – 1 – c[j]$。
Java 代码：
class Solution {
int N = 30010, M = 60010, idx = 0, n;
int[] he = new int[N], e = new int[M], ne = new int[M];
int[] f = new int[N], c = new int[N], g = new int[N];
void add(int a, int b) {e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
public int[] sumOfDistancesInTree(int _n, int[][] es) {
n = _n;
Arrays.fill(he, -1);
for (int[] e : es) {int a = e[0], b = e[1];
add(a, b); add(b, a);
}
dfs1(0, -1);
dfs2(0, -1);
int[] ans = new int[n];
for (int i = 0; i < n; i++) ans[i] = f[i] + g[i];
return ans;
}
int[] dfs1(int u, int fa) {
int tot = 0, cnt = 0;
for (int i = he[u]; i != -1; i = ne[i]) {int j = e[i];
if (j == fa) continue;
int[] next = dfs1(j, u);
tot += next[0] + next[1] + 1; cnt += next[1] + 1;
}
f[u] = tot; c[u] = cnt;
return new int[]{tot, cnt};
}
void dfs2(int u, int fa) {for (int i = he[u]; i != -1; i = ne[i]) {int j = e[i];
if (j == fa) continue;
g[j] += g[u] + n - 1 - c[u]; // 往上再往上
g[j] += f[u] - f[j] - c[j] + c[u] - 1 - c[j]; // 往上再往下
dfs2(j, u);
}
}
}- 工夫复杂度：$O(n)$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.834 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布