22 DEC 834. Sum of Distances in Tree

class Solution {
    vector<int>son,sonD,fatherD;
public:
    void sonDFS(vector<int> adj[], int i, int top){
        for(auto x : adj[i]){
            if(x == top) continue;
            sonDFS(adj,x, i);
            son[i] += son[x] + 1;
            sonD[i] += (sonD[x] + son[x] + 1);
        }
    }
    void fatherDFS(vector<int> adj[], int i, int top, int N){
        if(top != -1){
            fatherD[i] = fatherD[top] + (sonD[top] - sonD[i] - son[i] - 1) + (N - son[i] - 1);
        }
        
        for(auto x : adj[i]){
            if(x == top) continue;
            fatherDFS(adj, x, i, N);
        }
    }
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        son.resize(n, 0);
        sonD.resize(n, 0);
        fatherD.resize(n,0);

        vector<int> adj[n];
        for(auto x : edges){
            adj[x[0]].push_back(x[1]);
            adj[x[1]].push_back(x[0]);
        }

        sonDFS(adj, 0, -1);
        fatherDFS(adj, 0, -1, n);

        vector<int>res(n);
        for(int i=0;i<n;i++){
            res[i] = sonD[i] + fatherD[i];
        }
        return res;
    }
};