首页 > 代码库 > bzoj4928: 第二题
bzoj4928: 第二题
Description
对于一棵有根树，定义一个点u的k-子树为u的子树中距离u不超过k的部分。
注意，假如u的子树中不存在距离u为k的点，则u的k-子树是不存在的。
定义两棵子树是相同的，当且仅当不考虑点的标号时，他们的形态是
相同的（儿子的顺序也需要考虑）。给定一棵n个点，点的标号在[1,n]，
以1为根的有根树。问最大的k，使得存在两个点u !=v，满足u的k-子树与v的k-子树相同。
Input
第一行输入一个正整数n。
接下来读入n个部分，第i个部分描述点i的儿子，且以顺序给出。
每个部分首先读入一个整数x，代表儿子个数。
接下来x个整数，代表从左到右儿子的标号
n ≤ 100000，保证给出的树是合法的
Output
输出一个整数k，代表最大的合法的k
已知每个点的a-子树和b-子树的hash，可以推出每个点的(a+b)-子树的hash
对答案倍增，hash判定
#include<cstdio>#include<cstring>#define Fe(i,l,r) for(int i=l;i<=r;++i)typedef unsigned long long u64;const int N=100007,P=293999;void maxs(int&a,int b){if(a<b)a=b;}u64 H(u64 x){return (x^x>>17^x<<43)+777;}char buf[70007],*ptr=buf+70000;int G(){ if(ptr-buf==70000)fread(ptr=buf,1,70000,stdin); return *ptr++;}int _(){ int x=0; if(ptr-buf<69900){ while(*ptr<48)++ptr; while(*ptr>47)x=x*10+*ptr++-48; }else{ int c=G(); while(c<48)c=G(); while(c>47)x=x*10+c-48,c=G(); } return x;}int n,ans=1;int mem[N],*mp=mem,*e[N],ep[N],fa[20][N],fas[N],id[N],_fa[N],_son[N];int q[N],ql=0,qr=0,dep[N],md[N];u64 h[20][N],h2[N],_h[N];u64 hx[P];int ht[P],tk=1;bool ins(u64 x){ int w=(unsigned(x)^unsigned(x>>32))%P; while(ht[w]==tk){ if(hx[w]==x)return 1; if((w+=1237)>=P)w-=P; } hx[w]=x;ht[w]=tk; return 0;}template<class T>void cpy(T*a,T*b){memcpy(a+1,b+1,sizeof(T)*n);}void getson(){ memset(_son+1,0,sizeof(int)*n); Fe(t,1,qr){ int w=q[t],f=fas[w]; if(!_son[f])_son[f]=t; }}void cal(int _i){ cpy(_h,h[_i]); cpy(_fa,fa[_i]); for(int i=_i-1;i>=0;--i){ ++tk; cpy(h2,_h); getson(); Fe(t,1,qr){ int w=q[t],f=_fa[w]; if(f)h2[f]=h2[f]*1844677+h[i][w]+(id[fa[0][w]]-_son[f]); } bool is=0; int mn=ans+(1<<i); Fe(w,1,n)if(md[w]+1>=mn&&ins(h2[w])){ is=1; break; } if(is){ ans=mn; Fe(w,1,n){ _h[w]=H(h2[w]); _fa[w]=fa[i][_fa[w]]; fas[w]=fa[i][fas[w]]; } } }}void cal(){ Fe(w,1,n)h[0][w]=20120123103141; for(int i=0;i<19;++i){ ++tk; cpy(h2,h[i]); getson(); Fe(t,1,qr){ int w=q[t],f=fa[i][w]; if(f)h2[f]=h2[f]*1844677+h[i][w]+(id[fa[0][w]]-_son[f]); } bool is=0; int mn=ans+(1<<i); Fe(w,1,n)if(md[w]+1>=mn&&ins(h2[w])){ is=1; break; } if(is){ ans=mn; Fe(w,1,n){ h[i+1][w]=H(h2[w]); fa[i+1][w]=fa[i][fa[i][w]]; fas[w]=fa[i][fas[w]]; } }else return cal(i); }}int main(){ n=_(); for(int i=1;i<=n;++i){ fas[i]=i; e[i]=mp; mp+=ep[i]=_(); for(int j=0;j<ep[i];++j)fa[0][e[i][j]=_()]=i; } for(q[++qr]=1;fa[0][q[1]];++q[1]); while(ql!=qr){ int w=q[++ql]; id[w]=ql; for(int*l=e[w],*r=l+ep[w];l!=r;++l)dep[q[++qr]=*l]=dep[w]+1; } for(int i=qr;i;--i){ int w=q[i]; maxs(md[fa[0][w]],md[w]+1); } cal(); printf("%d\n",ans-1); return 0;}
bzoj4928: 第二题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。