834

class Solution {
public:
    vector<unordered_set<int>> g;
    vector<int> dp, count;
    int n;

    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
        dp.assign(N, 0);
        count.assign(N, 1);
        g.resize(N);
        n = N;

        // Create adj list.
        for(int i=0; i<edges.size(); i++){
            g[edges[i][0]].insert(edges[i][1]);
            g[edges[i][1]].insert(edges[i][0]);
        }

        // Create initial dp with dp[root] as overall answer.
        dfs1(0, -1);

        // Manipulate dp for each node and find it's answer.
        dfs2(0, -1);
        return dp;
    }

    void dfs1(int node, int parent){
        for(int child: g[node]){
            if(child == parent) continue;
            dfs1(child, node);
            count[node] += count[child];
            dp[node] += (dp[child]+count[child]);
        }
    }

    void dfs2(int node, int parent){
        for(int child: g[node]){
            if(child == parent) continue;
            // For each child, subtract the size of child's subtree as these many are downward edges from parent.
            // Also add (N-count[child]), these are number of nodes that exist in upward tree.
            dp[child] = dp[node]-count[child] + n-count[child];
            dfs2(child, node);
        }
    }

};