YEZAELP

LeetCode: Sum of Distances in Tree

Nov 30th, 2021 (edited)
681
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     vector <int> g[300010];
  5.     int node[300010], dpchild[300010];
  6.     bool vs[300010];
  7.  
  8.     void dfs(int u, int p){
  9.         if(vs[u]) return;
  10.         vs[u] = true;
  11.         node[u] = 1;
  12.         dpchild[u] = 0;
  13.         for(auto v: g[u]){
  14.             if(p != v){
  15.                 dfs(v, u);
  16.                 node[u] += node[v];
  17.                 dpchild[u] += dpchild[v] + node[v];
  18.             }
  19.         }
  20.     }
  21.    
  22.     void DP(int u, int p, vector <int> &dp, int n){
  23.         if(vs[u]) return;
  24.         vs[u] = true;
  25.         int dppar = (dp[p] - dpchild[u] - node[u]) + (n - node[u]); /// dpchild + node
  26.         dp[u] = dpchild[u] + (u == 0 ? 0 : dppar);
  27.         for(auto v: g[u]){
  28.             if(v != p) DP(v, u, dp, n);
  29.         }
  30.     }
  31.    
  32.     vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
  33.         int sz = edges.size();
  34.         for(int i=0;i<=sz-1;i++){
  35.             int u = edges[i][0];
  36.             int v = edges[i][1];
  37.             g[u].push_back(v);
  38.             g[v].push_back(u);
  39.         }
  40.  
  41.         for(int u=0;u<=n-1;u++) vs[u] = false;
  42.         dfs(0, 0);
  43.  
  44.         vector <int> dp(n, 0);
  45.         for(int u=0;u<=n-1;u++) vs[u] = false;
  46.         DP(0, 0, dp, n);
  47.        
  48.         return dp;
  49.     }
  50. };
RAW Paste Data