原题地址（困难）

    这题实在太难了！根本不会，直接看的官方题解。

    1. class Solution {
    2. public:
    3.     vector<int> ans, sz, dp;
    4.     vector<vector<int>> graph;
    6.     void dfs(int u, int f) {
    7.         sz[u] = 1;
    8.         dp[u] = 0;
    9.         for (auto& v: graph[u]) {
    10.             if (v == f) {
    11.                 continue;
    12.             }
    13.             dfs(v, u);
    14.             dp[u] += dp[v] + sz[v];
    15.             sz[u] += sz[v];
    16.         }
    17.     }
    19.     void dfs2(int u, int f) {
    20.         ans[u] = dp[u];
    21.         for (auto& v: graph[u]) {
    22.             if (v == f) {
    23.                 continue;
    24.             }
    25.             int pu = dp[u], pv = dp[v];
    26.             int su = sz[u], sv = sz[v];
    28.             dp[u] -= dp[v] + sz[v];
    29.             sz[u] -= sz[v];
    30.             dp[v] += dp[u] + sz[u];
    31.             sz[v] += sz[u];
    33.             dfs2(v, u);
    35.             dp[u] = pu, dp[v] = pv;
    36.             sz[u] = su, sz[v] = sv;
    37.         }
    38.     }
    40.     vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
    41.         ans.resize(N, 0);
    42.         sz.resize(N, 0);
    43.         dp.resize(N, 0);
    44.         graph.resize(N, {});
    45.         for (auto& edge: edges) {
    46.             int u = edge[0], v = edge[1];
    47.             graph[u].emplace_back(v);
    48.             graph[v].emplace_back(u);
    49.         }
    50.         dfs(0, -1);
    51.         dfs2(0, -1);
    52.         return ans;
    53.     }
    54. };