树形DP

LeetCode

834. 树中距离之和

不会，看不懂官方题解，这是比较容易理解的答案
对于两个相邻节点A和B，将树拆分为两个子树，根节点分别为A和B，A节点到其他所有节点的距离和可以分为三部分来计算，第一个是A子树中所有子节点到根节点A的距离和，第二个是B子树中所有子节点到另一个根节点B的距离和，第三个是B这棵子树中所有节点的数量。因此，得出如下两个公式：

因此，可以推出两个相邻节点的解的关系为

只要知道节点0的距离和，那就可以通过DFS或者BFS遍历的方式求出其他节点的距离和。
接下来就是求根节点0的距离和，而各子树的距离和相当于是递归计算。

//距离和
int[] res;
//根节点为0的情况下，各节点的子树中节点数量
int[] cnt;
//图
List<List<Integer>> graph;
int n;
public int[] sumOfDistancesInTree(int N, int[][] edges) {
    if (N <= 0) return null;
    res = new int[N];
    cnt = new int[N];
    n = N;
    graph = new ArrayList();
    //初始化图
    for (int i = 0; i < N; i++) {
        graph.add(new ArrayList<Integer>());
        cnt[i] = 1;
    }
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1];
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    //计算节点0的距离和
    dfs(-1, 0);
    System.out.println(Arrays.toString(res));
    System.out.println(Arrays.toString(cnt));
    //dfs反推其他节点的距离和
    dfs2(-1, 0);
    return res;
}
//计算某个根节点cur的距离和，需要明白根节点一旦确定，整棵树的父子节点关系也就确定了
public void dfs (int parent, int cur) {
    List<Integer> childs = graph.get(cur);
    for (int i = 0; i < childs.size(); i++) {
        if (childs.get(i) == parent)   continue;
        int child = childs.get(i);
        dfs(cur, child);
        cnt[cur] += cnt[child];
        res[cur] += res[child] + cnt[child];
    }
}
public void dfs2 (int parent, int cur) {
    List<Integer> childs = graph.get(cur);
    for (int i = 0; i < childs.size(); i++) {
        if (childs.get(i) == parent)   continue;
        int child = childs.get(i);
        //这里只能是cnt[child]，而不能直接使用cnt[cur]
        res[child] = res[cur] - cnt[child] + (n - cnt[child]);
        dfs2(cur, child);
    }
}