Advertisement
Josif_tepe

Untitled

Oct 19th, 2023
759
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. const int maxn = 2e5 + 10;
  6. typedef long long ll;
  7. int n;
  8. vector<int> graph[maxn];
  9. ll subtree[maxn];
  10. ll dist[maxn];
  11. void subtree_size(int node, int parent, int depth) {
  12.     subtree[node] = 1;
  13.     dist[0] += depth;
  14.     for(int neighbour : graph[node]) {
  15.         if(neighbour != parent) {
  16.             subtree_size(neighbour, node, depth + 1);
  17.             subtree[node] += subtree[neighbour];
  18.         }
  19.     }
  20. }
  21. void dfs(int node, int parent) {
  22.     for(int neighbour : graph[node]) {
  23.         if(neighbour != parent) {
  24.             dist[neighbour] = dist[node] + n - 2 * subtree[neighbour];
  25.             dfs(neighbour, node);
  26.         }
  27.     }
  28. }
  29.  
  30. int main()
  31. {
  32.     ios_base::sync_with_stdio(false);
  33.     cin >> n;
  34.    
  35.     for(int i = 1; i < n; i++) {
  36.         int a, b;
  37.         cin >> a >> b;
  38.         a--; b--;
  39.         graph[a].push_back(b);
  40.         graph[b].push_back(a);
  41.     }
  42.     subtree_size(0, -1, 0);
  43.     dfs(0, -1);
  44.     for(int i = 0; i < n; i++) {
  45.         cout << dist[i] << " ";
  46.     }
  47.     return 0;
  48. }
  49.  
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement