Advertisement
willy108

CSES_1133

Nov 10th, 2020 (edited)
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <vector>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <queue>
  9. #define max_v 210000
  10. #define cont continue
  11. using namespace std;
  12.  
  13. vector<int> adj[max_v];
  14. long long ans[max_v];
  15. int sub[max_v], par[max_v];
  16.  
  17. long long dist = 0ll, n;
  18.  
  19. int dfs(int u, int d, int p){
  20.     par[u] = p;
  21.     dist += (long long)d;
  22.     for(int v : adj[u]){
  23.         if(v == p) cont;
  24.         sub[u] += dfs(v, d + 1, u);
  25.     }
  26.     sub[u]++;
  27.     return  sub[u] ;
  28. }
  29.  
  30. void bfs(){
  31.     queue<int> q;
  32.     q.push(1);
  33.     ans[1] = dist;
  34.     while(!q.empty()){
  35.         int u = q.front(); q.pop();
  36.         for(int v : adj[u]){
  37.             if(v == par[u]) cont;
  38.             ans[v] = ans[u] + (long long)((n - sub[v]) - sub[v]);
  39.             q.push(v);
  40.         }
  41.     }
  42. }
  43.  
  44.  
  45. int main(){
  46.     scanf("%d", &n);
  47.     for(int i = 0; i<n - 1; i++){
  48.         int a, b;
  49.         scanf("%d%d", &a, &b);
  50.         adj[a].push_back(b);
  51.         adj[b].push_back(a);
  52.     }
  53.     dfs(1, 0, 0);
  54.     bfs();
  55.     for(int i = 1; i<=n; i++){
  56.         printf("%lld ", ans[i]);
  57.     }
  58.     return 0;
  59. }
  60.  
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement