普通子樹哈希

樹上的很多東西都是轉(zhuǎn)化成鏈上問(wèn)題的，比如樹上哈希
樹上哈希，主要是用于樹的同構(gòu)這個(gè)東西上的
什么是樹的同構(gòu)？

如圖，不考慮節(jié)點(diǎn)編號(hào)，三棵樹是同構(gòu)的

將樹轉(zhuǎn)化成鏈，一般有兩種方式：環(huán)游歐拉序與歐拉序
為了盡可能減少哈希沖突，進(jìn)制位越小越好
又因?yàn)椴豢紤]節(jié)點(diǎn)編號(hào)，很明顯，若是采用歐拉序的話，得要記錄該節(jié)點(diǎn)孩子數(shù)
環(huán)游歐拉序只用進(jìn)入打上1，出來(lái)打上2即可搞定
小tips：歐拉序相較于環(huán)游歐拉序可能更快，請(qǐng)量力而行

于是，就可以采用普通的哈希方式啦！

指定范圍子樹哈希

如果說(shuō)是將子樹橫著割一刀呢？
如圖，是一棵樹

放心，就60個(gè)節(jié)點(diǎn)
我們考慮D節(jié)點(diǎn)的子樹中，距離D不超過(guò)3的所有點(diǎn)
如圖

接著是環(huán)游歐拉序（考慮在某些原因的份上，我只保留D的子樹）

為什么我只寫到10？因?yàn)樽髡邔?shí)在太懶因?yàn)榈?0就夠了
對(duì)于范圍樹上哈希，我們有兩種方式——拼接與刪除
因?yàn)楣Ｒ话阍谌∧５囊饬x下，所以，刪除是非常難以做到的~~（作者親測(cè)過(guò)）~~
那只剩下拼接了，這個(gè)就和鏈上拼接一模一樣了（也很像是前綴和）

模板題

題目主要考的是范圍樹上哈希

如果說(shuō)看懂了前面的，這題就不難了。首先可以二分。因?yàn)槿羰?span id="ieo6y2aa" class="katex--inline">$k$是答案，那么一定存在兩個(gè)節(jié)點(diǎn)的$k$層子樹是同構(gòu)的。在其中任選兩個(gè)對(duì)應(yīng)的點(diǎn)，所組成的子樹的子樹一定是同構(gòu)的
這么說(shuō)顯得很煩，翻譯成人化就是：對(duì)于每個(gè)符合題目要求的$k$層的兩個(gè)子樹（就是這兩個(gè)字叔同構(gòu)），他們的所有子樹中一定有同構(gòu)的，并且層數(shù)有$0$、有$1$、有$?$、有$k?1$

于是，題目就這樣轉(zhuǎn)化成了求是否存在同構(gòu)的$k$層子樹
我們可以對(duì)于每個(gè)節(jié)點(diǎn)，求出它的$k$層祖先，代表這個(gè)節(jié)點(diǎn)絕對(duì)存在$k$層子樹；
再找出$k+1$曾祖先，代表這個(gè)節(jié)點(diǎn)的子樹將要在他的祖先的子樹中被刪去（不被添加）
最后用一個(gè)map（建議使用gp_hash_table）統(tǒng)計(jì)答案
題目就這么結(jié)束了

代碼

#pragma GCC optimize(1, "inline", "Ofast")
#pragma GCC optimize(2, "inline", "Ofast")
#pragma GCC optimize(3, "inline", "Ofast")
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
namespace IO {
class input {
private:bool isdigit(char c) { return ('0' <= c && c <= '9'); }public:input operator>>(int &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(short &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(bool &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(long long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(__int128 &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned int &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned short &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned long long &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(unsigned __int128 &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();if (!y)x = -x;return *this;}input operator>>(double &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();if (!y)x = -x;if (!isdigit(c))if (c != '.')return *this;double z = 1;while (isdigit(c)) z /= 10., x = x + z * (c ^ 48), getchar();return *this;}input operator>>(long double &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();if (!y)x = -x;if (!isdigit(c))if (c != '.')return *this;double z = 1;while (isdigit(c)) z /= 10., x = x + z * (c ^ 48), c = getchar();return *this;}input operator>>(float &x) {x = 0;bool y = 1;char c = getchar();while (!isdigit(c)) y &= (c != '-'), c = getchar();while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();if (!y)x = -x;if (!isdigit(c))if (c != '.')return *this;double z = 1;while (isdigit(c)) z /= 10., x = x + z * (c ^ 48), c = getchar();return *this;}input operator>>(std::string &x) {char c = getchar();x.clear();while (!(c != ' ' && c != '\n' && c != '	' && c != EOF && c)) c = getchar();while (c != ' ' && c != '\n' && c != '	' && c != EOF && c) {x.push_back(c);c = getchar();}return *this;}input operator>>(char *x) {char c = getchar();int cnt = 0;while (!(c != ' ' && c != '\n' && c != '	' && c != EOF && c)) c = getchar();while (c != ' ' && c != '\n' && c != '	' && c != EOF && c) {x[cnt++] = c;c = getchar();}return *this;}input operator>>(char x) {x = getchar();return *this;}
} pin;
};  // namespace IO
inline void wt(char ch) { putchar(ch); }
template <class T>
inline void wt(T x) {static char ch[40];int p = 0;if (x < 0)putchar('-'), x = -x;doch[++p] = (x % 10) ^ 48, x /= 10;while (x);while (p) putchar(ch[p--]);
}
template <class T, class... U>
inline void wt(T x, U... t) {wt(x), wt(t...);
}
#define int unsigned long long
const int N = 1e5 + 7;
int n;
const int M = 2e5 + 7;
struct edge {int v, w, nxt;
} e[M];
int head[N], ct;
const int T = 19, K = 3;
int ll[N], x[M], nx[N];//x一定要開兩倍！！！
int l[N], r[N];
int tp;
int getpw(int d) { return ll[d]; }
void addE(int u, int v, int w = 0) {e[++ct] = { v, w, head[u] };head[u] = ct;
}
void saddE(int u, int v, int w = 0) { addE(u, v, w), addE(v, u, w); }
int fa[N][T + 1];
__gnu_pbds::gp_hash_table<int, bool> cun;
void getx(int u = 1, int faa = 0) {l[u] = ++tp;x[tp] = (x[tp - 1] * K + 1);fa[u][0] = faa;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].v;getx(v, u);}r[u] = ++tp;x[tp] = (x[tp - 1] * K + 2);
}
int ytl[N];
typedef pair<int, int> pii;
vector<pii> vt[N];
bool chk(int mid) {memset(nx, 0, sizeof nx);cun.clear();memset(ytl, 0, sizeof ytl);for (int i = 1; i <= n; i++) vt[i].clear();for (int i = 1; i <= n; i++) {int tl = i;for (int j = T, k = mid; ~j; j--)if ((1ull << j) <= k)k -= (1ull << j), tl = fa[tl][j];if (tl == 0)continue;ytl[tl] = 1;tl = fa[tl][0];if (tl == 0)continue;// out<<i<<" "<<tl<<endl;vt[tl].push_back(pii(l[i], i));}for (int i = 1; i <= n; i++) sort(vt[i].begin(), vt[i].end());bool flg = 0;for (int i = 1; i <= n; i++) {if (!ytl[i])continue;int lr = l[i];for (auto j : vt[i]) {int k = j.second;//	cout<<k<<endl;(nx[i] *= getpw(l[k] - lr));(nx[i] += x[l[k] - 1] - (x[lr - 1] * getpw(l[k] - lr)));//	cout<<x[l[k]-1]<<" "<<x[lr-1]<<" "<<nx[i]<<endl;lr = r[k] + 1;}(nx[i] *= getpw(r[i] - lr + 1));(nx[i] += x[r[i]] - (x[lr - 1] * getpw(r[i] - lr + 1)));if (cun[nx[i]])return 1;// cout<<nx[i]<<endl;cun[nx[i]] = 1;//	cout<<nx[i]<<endl;//	puts("");}return flg;
}
main() {freopen("tree.in", "r", stdin);freopen("tree.out", "w", stdout);ll[0] = 1;for (int i = 1; i < N; i++) ll[i] = (ll[i - 1] * K);IO::pin >> n;for (int i = 1, x, y; i <= n; i++) {IO::pin >> x;while (x--) IO::pin >> y, addE(i, y);}getx();for (int j = 1; j <= T; j++)for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];int l = 0, r = n - 1;while (l < r) {int mid = l + r + 1 >> 1;// cout<<l<<" "<<r<<" "<<mid<<endl;if (chk(mid))l = mid;elser = mid - 1;}printf("%llu\n", l);
}