paulomiranda98

Tree Distances II

Oct 29th, 2020
889
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define all(x) x.begin(),x.end()
  5. #define endl '\n'
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. const int INF = 0x3f3f3f3f;
  12. const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  13. const int MOD = 1000000007;
  14. const int MAXN = 200010;
  15.  
  16. vector<int> adj[MAXN];
  17. ll down[MAXN], up[MAXN], sz[MAXN];
  18. void dfs1(int u, int p){
  19.   sz[u] = 1;
  20.   down[u] = 0;
  21.   for(int to: adj[u]){
  22.     if(to == p) continue;
  23.     dfs1(to, u);
  24.     sz[u] += sz[to];
  25.     down[u] += (down[to] + sz[to]);
  26.   }
  27. }
  28. int n;
  29. void dfs2(int u, int p){
  30.   for(int to: adj[u]){
  31.     if(to == p) continue;
  32.     ll aux = down[u] - (sz[to] + down[to]) + up[u];
  33.     up[to] = (aux + n-sz[to]);
  34.     dfs2(to, u);
  35.   }
  36. }
  37.  
  38. int main() {
  39.   ios_base::sync_with_stdio(false); cin.tie(NULL);
  40.   cin >> n;
  41.   for(int i=0; i<n-1; i++){
  42.     int a, b;
  43.     cin >> a >> b;
  44.     adj[a].push_back(b);
  45.     adj[b].push_back(a);
  46.   }
  47.   dfs1(1, 0);
  48.   dfs2(1, 0);
  49.   for(int i=1; i<=n; i++)
  50.     cout << (down[i] + up[i]) << " ";
  51.   cout << endl;
  52.   return 0;
  53. }
  54.  
RAW Paste Data