这题一看就可以二分 那么解决这题的关键就变成了怎么对树进行哈希，以及怎么快速维护哈希值 想了一个下午想了一个比较靠谱的哈希方法。 用一个p进制数(p>n且为质数)来表示每一个节点，这个数有depth位，depth位这个节点的深度，那么这个数在p进制下第i位表示这个点的depth-i的祖先是其父亲的第几个儿子。
大概长这样 子树中所有节点的哈希值之和作为这个子树的哈希值。 因为每个哈希值的组合表示了唯一一颗子树，那么出现哈希值重合但是不同构的子树的概率就很小了
在二分中检验的时候，dfs一遍，可以用按深度建可并堆来维护K-子树，每次合并子树的可并堆，并在子树可并堆上打个乘p+tag的标记，并且把深度超过二分的d时弹出堆，然后用map记一下哈希值就可以了。
轻松垫底
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <string> #include <cstring> using namespace std; const int N=100010,base=100003; typedef unsigned long long ll; int n,x,u,cnt; int depth[N]; vector<int> son[N],l[N]; map<ll,int> M; struct iheap{ iheap *l,*r; ll val,mul,add,key; int deep,size; }h[N],*rt[N]; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void rea(int &x){ char c=nc(); x=0; for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc()); } void dfs(int x){ for(int i=0;i<son[x].size();i++) depth[son[x][i]]=depth[x]+1,dfs(son[x][i]); } inline void Mul(iheap *x,ll y){ if(!x) return ; x->val*=y; x->mul*=y; x->add*=y; x->key*=y; } inline void Add(iheap *x,ll y){ if(!x) return ; x->val+=y*x->size; x->add+=y; x->key+=y; } inline void Push(iheap *x){ if(x->mul!=1) Mul(x->l,x->mul),Mul(x->r,x->mul),x->mul=1; if(x->add) Add(x->l,x->add),Add(x->r,x->add),x->add=0; } inline void Up(iheap *x){ x->size=(x->l?x->l->size:0)+(x->r?x->r->size:0)+1; x->val=(x->l?x->l->val:0)+(x->r?x->r->val:0)+x->key; } inline int ran(){ static int x=31253125; x+=(x<<4)+1; return x&65536; } iheap *Merge(iheap *x,iheap *y){ if(!x||!y) return !x?y:x; if(x->deep<y->deep) return Merge(y,x); Push(x); Push(y); if(ran()) x->l=Merge(x->l,y); else x->r=Merge(x->r,y); return Up(x),x; } bool check(int x,int d){ for(int i=0;i<son[x].size();i++){ if(check(son[x][i],d)) return true; Mul(rt[son[x][i]],base); Add(rt[son[x][i]],i+1); rt[x]=Merge(rt[x],rt[son[x][i]]); } h[++cnt].val=h[cnt].key=0; h[cnt].deep=depth[x]; h[cnt].mul=1; h[cnt].add=0; h[cnt].l=h[cnt].r=0; h[cnt].size=1; rt[x]=Merge(rt[x],h+cnt); while(rt[x] && rt[x]->deep>depth[x]+d) Push(rt[x]),rt[x]=Merge(rt[x]->l,rt[x]->r); if(!rt[x]||rt[x]->deep!=depth[x]+d) return false; return M.count(rt[x]->val)?true:(M[rt[x]->val]=1,false); } inline void Clear(){ M.clear(); cnt=0; for(int i=1;i<=n;i++) rt[i]=0; } int main(){ rea(n); for(int i=1;i<=n;i++) for(rea(x);x;x--) rea(u),son[i].push_back(u); dfs(1); int L=1,R=n,mid,ans=0,sx=0; while(L<=R) (Clear(),check(1,mid=L+R>>1))?L=(ans=mid)+1:R=mid-1; printf("%d\n",ans); return 0; }