#include using namespace std; #define ll long long #define elif else if #define vi vector #define vll vector #define vvi vector #define pii pair #define repname(a, b, c, d, e, ...) e #define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__) #define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter) #define rep1(i, x) for (int i = 0; i < (x); ++i) #define rep2(i, l, r) for (int i = (l); i < (r); ++i) #define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c)) template ostream &operator<<(ostream &os, const set s) { os << "{"; bool first = true; for (const auto &x : s) { if (!first) os << ", "; os << x; first = false; } os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set s) { os << "{"; bool first = true; for (const auto &x : s) { if (!first) os << ", "; os << x; first = false; } os << "}"; return os; } template ostream &operator<<(ostream &os, const map m) { os << "{"; bool first = true; for (const auto &[key, value] : m) { if (!first) os << ", "; os << key << ": " << value; first = false; } os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map m) { os << "{"; bool first = true; for (const auto &[key, value] : m) { if (!first) os << ", "; os << key << ": " << value; first = false; } os << "}"; return os; } template ostream &operator<<(ostream &os, const array a) { os << "("; for (size_t i = 0; i < N; ++i) { if (i > 0) os << ", "; os << a[i]; } os << ")"; return os; } template ostream &operator<<(ostream &os, const pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template ostream &operator<<(ostream &os, const vector v) { os << "["; for (int i = 0; i < v.size(); ++i) { if (i > 0) os << ", "; os << v[i]; } os << "]"; return os; } template void print(T x) { cout << x << '\n'; } template void print(Head &&head, Tail &&...tail) { cout << head << ' '; print(forward(tail)...); } // ----------------------------------------------- struct LCA { int n; vvi G, st; vi dep, S, FS; int LOG(int i) { return 31 - __builtin_clz(i); } LCA(int n, vvi &G, int root) : n(n), G(G), dep(n, -1), FS(n) { dep[root] = 0; dfs(root, -1); int L = S.size(); st.resize(LOG(L) + 1); st[0] = S; int b = 1; rep(i, LOG(L)) { int sz = st[i].size() - b; st[i + 1].resize(sz); rep(j, sz) { int u = st[i][j]; int v = st[i][j + b]; st[i + 1][j] = (dep[u] <= dep[v]) ? u : v; } b *= 2; } } void dfs(int v, int p) { FS[v] = S.size(); S.push_back(v); for (auto u : G[v]) { if (u != p) { dep[u] = dep[v] + 1; dfs(u, v); S.push_back(v); } } } int lca(int u, int v) { int x = FS[u], y = FS[v]; if (x > y) swap(x, y); int l = LOG(y - x + 1); int px = st[l][x], py = st[l][y - (1 << l) + 1]; return (dep[px] <= dep[py]) ? px : py; } }; /* - `AuxiliaryTree T(n, edge, 0);` で初期化 - 頂点列 `vector vs` に対して `int r = T.query(vs);` で補助的な木の根が返る.`vector T.G[v]` にその補助的な木に含まれる頂点の子が格納されている. */ struct AuxiliaryTree { int n, dum; vi L, R, last, par; // L, R: eular tour 上で頂点 v が登場する最初/最後の位置 vvi edge, G; LCA lca; AuxiliaryTree(int n, vvi edge, int root) : n(n), edge(edge), G(n), lca(n, edge, root), L(n, 0), R(n, 0), last(n, -1), par(n, -1) { dum = 0; dfs(0, -1); }; void dfs(int v, int p) { par[v] = p; L[v] = dum; dum++; for (auto u : edge[v]) if (u != p) dfs(u, v); R[v] = dum; dum++; } int query(vi vs) { assert(vs.size() != 0); sort(vs.begin(), vs.end(), [&](int u, int v) { return L[u] < L[v]; }); // pre-order で sort int sz = vs.size(); rep(i, sz - 1) vs.push_back(lca.lca(vs[i], vs[i + 1])); sort(vs.begin(), vs.end(), [&](int u, int v) { return L[u] < L[v]; }); // pre-order で sort vi stc; int prv = -1; for (auto v : vs) { if (prv == v) continue; prv = v; while (!stc.empty() && R[stc.back()] < L[v]) stc.pop_back(); if (!stc.empty()) G[stc.back()].push_back(v); G[v].clear(); stc.push_back(v); } return stc[0]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(20); int n; cin >> n; vvi G(n); vvi E(n - 1); rep(v, n) { int c; cin >> c; rep(c) { int e; cin >> e; e--; E[e].push_back(v); } } rep(e, n - 1) { int u = E[e][0], v = E[e][1]; G[u].push_back(v); G[v].push_back(u); } AuxiliaryTree AT(n, G, 0); vi par = AT.par; vector> deg; rep(i, n) { deg.push_back({G[i].size(), i}); } sort(deg.rbegin(), deg.rend()); rep(q, 1, n) { vi vs; for (auto [d, v] : deg) { if (d >= q) vs.push_back(v); else break; } if (vs.size() == 0) { cout << "0" << " \n"[q + 1 == n]; continue; } int r = AT.query(vs); unordered_map mp; int ans = 0; auto dfs = [&](auto dfs, int v) -> void { for (auto u : AT.G[v]) { dfs(dfs, u); } int x = (int)G[v].size() - mp[v]; if (x >= q) { ans++; if (v != 0 && x == q) { mp[par[v]]++; } } }; dfs(dfs, r); cout << ans << " \n"[q + 1 == n]; } }