Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define all(a) a.begin(), a.end()
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- typedef long double ld;
- #define int long long
- #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
- vector<vector<int>> gr;
- const int N = 2e5 + 1;
- ordered_set dep[N];
- vector<int> ans;
- void dfs(int v, int p) {
- dep[v].insert(v);
- for (int& u : gr[v]) {
- if (u != p) {
- dfs(u, v);
- bool ok = 1;
- if (dep[u].size() > dep[v].size()) {
- dep[u].swap(dep[v]);
- ok = 0;
- }
- for (auto& it : dep[u]) {
- dep[v].insert(it);
- if (ok) {
- ans[v] += dep[v].size() - 1 - dep[v].order_of_key(it);
- }
- else {
- ans[v] += dep[v].order_of_key(it);
- }
- dep[v].erase(it);
- }
- for (auto& it : dep[u]) {
- dep[v].insert(it);
- }
- dep[u].clear();
- ans[v] += ans[u];
- }
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n; cin >> n;
- gr.resize(n); ans.resize(n);
- for (int i = 0; i < n; i++) {
- int k; cin >> k;
- for (int j = 0; j < k; j++) {
- int x; cin >> x; --x;
- gr[i].push_back(x);
- gr[x].push_back(i);
- }
- }
- dfs(0, -1);
- for (int i = 0; i < n; i++) {
- cout << ans[i] << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement