LEET-T0834: Sum of Distances in Tree

#include <bits/stdc++.h>
using namespace std;

const int N = 3e4 + 5;

vector<vector<int>> edges;
vector<int> adj[N];
int subtree[N], dp[N], par[N];

void DFS(int u, int p){
    par[u] = p;
    subtree[u] = 1;
    dp[u] = 0;
    for(int v : adj[u]){
        if(v == p){
            continue;
        }
        DFS(v, u);
        subtree[u] += subtree[v];
        dp[u] += dp[v] + subtree[v];
    }
}

void DFSRev(vector<int> &ans, int nVertex, int u, int p){
    if(p == -1){
        ans[u] = dp[u];
    } else {
        ans[u] = nVertex + ans[p] - 2 * subtree[u];
    }
    for(int v : adj[u]){
        if(v == p){
            continue;
        }
        DFSRev(ans, nVertex, v, u);
    }
}

vector<int> sumOfDistancesInTree(int nVertex, vector<vector<int>> &edges){
    for(vector<int> &p: edges){
        int u = p[0];
        int v = p[1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    DFS(0, -1);
    vector<int> ans(nVertex, 0);
    DFSRev(ans, nVertex, 0, -1);
    return ans;
}

int main(){

    int nVertex;
    scanf("%d", &nVertex);
    for(int i = 1; i < nVertex; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        edges.push_back(vector<int>({u, v}));
    }
    for(int x : sumOfDistancesInTree(nVertex, edges)){
        cout << x << ' ';
    }

    return 0;
}