//#pragma GCC optimize("Ofast,unroll-loops") #ifdef LOCAL #include "debug.h" #else #include #include #include #define debug(x...) #endif using namespace std; //#define int ll typedef long long ll; typedef long double ld; typedef pair pii; #define sz(x) int((x).size()) template using ordered_set = __gnu_pbds::tree , __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; #ifdef ONLINE_JUDGE mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #else mt19937 rng(1000 - 7); #endif const int N = 2e5 + 10; //const int MOD = 998244353; const ll MOD = 1e9 + 7; const ld eps = 1e-9; const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; struct segtree { struct Node { Node *l = nullptr, *r = nullptr; int tl, tr, sum; Node(int tl, int tr) : tl(tl), tr(tr) {} ~Node() { delete l; delete r; } }; ~segtree() { delete root; } Node *root = new Node(0, N - 1); int _size = 0; inline int get(Node *u) { return (u ? u->sum : 0); } void update(Node *u, int pos) { if (u->tl == u->tr) { u->sum = 1; } else { int tm = (u->tl + u->tr) / 2; if (pos <= tm) { if (!u->l) { u->l = new Node(u->tl, tm); } update(u->l, pos); } else { if (!u->r) { u->r = new Node(tm + 1, u->tr); } update(u->r, pos); } u->sum = get(u->l) + get(u->r); } } int sum(Node *u, int l, int r) { if (l > r || !u) { return 0; } else if (u->tl == l && u->tr == r) { return u->sum; } else { int tm = (u->tl + u->tr) / 2; return sum(u->l, l, min(tm, r)) + sum(u->r, max(tm + 1, l), r); } } inline void insert(int x) { _size++; update(root, x); } inline int less_than(int x) { return sum(root, 0, x - 1); } inline int greater_than(int x) { return sum(root, x + 1, N - 1); } inline int size() { return _size; } void dfs(Node *u, vector & res) { if (u->l) { dfs(u->l, res); } if (u->r) { dfs(u->r, res); } if (u->tl == u->tr) { res.push_back(u->tl); } } vector get_list() { vector res; res.reserve(_size); dfs(root, res); return res; } }; int n; ll ans[N]; vector g[N]; ll merge(segtree& a, segtree& b) { ll add = 0; if (b.size() < a.size()) { auto v = b.get_list(); for (int x : v) { add += a.greater_than(x); } for (int x : v) { a.insert(x); } } else { auto v = a.get_list(); for (int x : v) { add += b.less_than(x); } for (int x : v) { b.insert(x); } swap(a, b); } return add; } segtree dfs(int u) { ll cur = 0; segtree s; s.insert(u); for (int v : g[u]) { auto t = dfs(v); cur += ans[v]; cur += merge(s, t); } ans[u] = cur; return s; } signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cout << fixed << setprecision(9); ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { int k; cin >> k; while (k--) { int v; cin >> v; g[i].push_back(v); } } dfs(1); for (int i = 1; i <= n; i++) { cout << ans[i] << " "; } return 0; }