fork download 
  1. //@memset.DP.-1
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. //--------------------------------WRITE_HERE-------------------------------------------
  7.  
  8. vector<int>g[200000+1];
  9. vector<int>subtree_size(200000+1);
  10. vector<ll>cost(200000+1);
  11. vector<ll>res(200000+1);
  12.  
  13. void preCalc(int node, int p)
  14. {   subtree_size[node]=1;
  15.     cost[node]=0;
  16.  
  17.     for(int &c:g[node]){
  18.         if(c!=p){
  19.             preCalc(c,node);
  20.             subtree_size[node] += subtree_size[c];
  21.             cost[node] += (cost[c]+subtree_size[c]);
  22.         }
  23.     }
  24. }
  25.  
  26. void dfs(int node,int p){
  27.     res[node]=cost[node];
  28.  
  29.     for(int &c:g[node]){
  30.         if(c!=p){
  31.             cost[node] -= (cost[c]+subtree_size[c]);
  32.             subtree_size[node] -= subtree_size[c];
  33.  
  34.             cost[c] += (cost[node]+subtree_size[node]);
  35.             subtree_size[c] += subtree_size[node];
  36.  
  37.             dfs(c, node);
  38.  
  39.             cost[c] -= (cost[node] + subtree_size[node]);
  40.             subtree_size[c] -= subtree_size[node];
  41.  
  42.             cost[node] += (cost[c] + subtree_size[c]);
  43.             subtree_size[node] += subtree_size[c];
  44.         }
  45.     }
  46. }
  47.  
  48. void _144()
  49. {
  50.     int n;cin>>n;
  51.  
  52.     for(int i=0;i<n-1;i++){
  53.         int a,b;cin>>a>>b;
  54.         g[a].push_back(b);
  55.         g[b].push_back(a);
  56.     }
  57.  
  58.     preCalc(1,-1);
  59.     dfs(1,-1);
  60.  
  61.     for(int i=1;i<=n;i++) cout<<res[i]<<" ";
  62.     return;
  63. }
  64.  
  65. //--------------------------------END--------------------------------------------------
  66.  
  67. // Main
  68. int main()
  69. {
  70. //freopen("input.in", "r",stdin);
  71. //freopen("output.out", "w",stdout);
  72.  
  73.     ios_base::sync_with_stdio(false);
  74.     cin.tie(NULL);
  75.     cout.tie(NULL);
  76.  
  77.     ll t = 1;
  78.     // cin >> t;
  79.     while (t--)
  80.     {
  81.         _144();
  82.     }
  83. }
Runtime error #stdin #stdout 0.04s 11840KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FOUW19
language:
C++ (gcc 8.3)
created:
74 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!