https://leetcode.com/problems/sum-of-distances-in-tree/submissions/

Rerooting Trees.

class Solution {
public:
    vector<int>ans;
    vector<int>cnt;
    vector<vector<int>>adj;
    void dfs(int i,int cur){
        for(auto a:adj[i]){
            if(a!=cur){
                dfs(a,i);
                cnt[i]+=cnt[a];
                ans[i]+=ans[a]+cnt[a];
            }
        }
    }
    void dfs1(int i,int cur,int n){
        for(auto a:adj[i])
        {
            if(a==cur)continue;
            ans[a] = ans[i]-cnt[a]+n-cnt[a];
            dfs1(a,i,n);
        }
    }
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        cnt.clear();
        cnt.resize(n,1);
        ans.clear();
        ans.resize(n,0);
        adj.clear();
        adj.resize(n,vector<int>());
        for(auto a:edges){
            adj[a[0]].push_back(a[1]);
            adj[a[1]].push_back(a[0]);
        }
        dfs(0,-1);
        dfs1(0,-1,n);
        return ans;
    }
};