Advertisement
ivnikkk

Untitled

Sep 27th, 2022
1,128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. #define all(a) a.begin(), a.end()
  8. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  9. typedef long double ld;
  10. #define int long long
  11. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  12. vector<vector<int>> gr;
  13. const int N = 2e5 + 1;
  14. ordered_set dep[N];
  15. vector<int> ans;
  16. void dfs(int v, int p) {
  17.     dep[v].insert(v);
  18.     for (int& u : gr[v]) {
  19.         if (u != p) {
  20.             dfs(u, v);
  21.             bool ok = 1;
  22.             if (dep[u].size() > dep[v].size()) {
  23.                 dep[u].swap(dep[v]);
  24.                 ok = 0;
  25.             }
  26.             for (auto& it : dep[u]) {
  27.                 dep[v].insert(it);
  28.                 if (ok) {
  29.                     ans[v] += dep[v].size() - 1 - dep[v].order_of_key(it);
  30.                 }
  31.                 else {
  32.                     ans[v] += dep[v].order_of_key(it);
  33.                 }
  34.                 dep[v].erase(it);
  35.             }
  36.             for (auto& it : dep[u]) {
  37.                 dep[v].insert(it);
  38.             }
  39.             dep[u].clear();
  40.             ans[v] += ans[u];
  41.         }
  42.     }
  43. }
  44. signed main() {
  45. #ifdef _DEBUG
  46.     freopen("input.txt", "r", stdin);
  47.     freopen("output.txt", "w", stdout);
  48. #endif
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(nullptr);
  51.     cout.tie(nullptr);
  52.     int n; cin >> n;
  53.     gr.resize(n); ans.resize(n);
  54.     for (int i = 0; i < n; i++) {
  55.         int k; cin >> k;
  56.         for (int j = 0; j < k; j++) {
  57.             int x; cin >> x; --x;
  58.             gr[i].push_back(x);
  59.             gr[x].push_back(i);
  60.         }
  61.     }
  62.     dfs(0, -1);
  63.     for (int i = 0; i < n; i++) {
  64.         cout << ans[i] << ' ';
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement