传送门

二分答案 \(k\)，考虑如何 \(hash\) 使得做起来方便

把每个点挂在 \(k+1\) 级祖先上，考虑在祖先上删除

这道题巧妙在于其可以对于 \(dfs\) 序/括号序列 \(hash\)

这样在 \(k+1\) 级祖先上暴力删除就好了

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn(2e5 + 5);

const ull base(19260817);

unordered_map <ull, int> hash_table;

int first[maxn], cnt, n, idx, dfn[maxn], ed[maxn], mxd[maxn], st[maxn], top;

ull val[maxn], pw[maxn], hsh[maxn];

vector <int> son[maxn], kson[maxn];

inline void Dfs1(int u) {

	dfn[u] = ++idx, val[idx] = 233;

	for (auto v : son[u]) Dfs1(v), mxd[u] = max(mxd[u], mxd[v]);

	ed[u] = ++idx, ++mxd[u], val[idx] = 131;

}

inline void Dfs2(int u, int k) {

	st[++top] = u;

	if (top - 1 > k) kson[st[top - k - 1]].push_back(u);

	for (auto v : son[u]) Dfs2(v, k);

	--top;

}

inline ull Hash(int l, int r) {

	return hsh[r] - hsh[l - 1] * pw[r - l + 1];

}

inline int Calc(int k) {

	register int i, l, r;

	register ull v;

	hash_table.clear();

	for (i = 1; i <= n; ++i) kson[i].clear();

	Dfs2(1, k);

	for (i = 1; i <= n; ++i)

		if (mxd[i] > k) {

			l = dfn[i], v = 0;

			for (auto to : kson[i]) {

				r = dfn[to] - 1;

				v = v * pw[r - l + 1] + Hash(l, r);

				l = ed[to] + 1;

			}

			r = ed[i], v = v * pw[r - l + 1] + Hash(l, r);

			if (hash_table.count(v)) return 1;

			hash_table[v] = 1;

		}

	return 0;

}

int main() {

	register int i, v, x, l, r, mid, ans;

	scanf("%d", &n);

	for (i = 1; i <= n; ++i)

		for (scanf("%d", &x); x; --x) scanf("%d", &v), son[i].push_back(v);

	Dfs1(1), pw[0] = 1;

	for (i = 1; i <= idx; ++i) pw[i] = pw[i - 1] * base;

	for (i = 1; i <= idx; ++i) hsh[i] = hsh[i - 1] * base + val[i];

	l = 2, r = n, ans = 1;

	while (l <= r) Calc(mid = (l + r) >> 1) ? ans = mid, l = mid + 1 : r = mid - 1;

	printf("%d\n", ans);

	return 0;

}