bzoj4754: [Jsoi2016]独特的树叶-白红宇

bzoj4754: [Jsoi2016]独特的树叶

阅读量：4326 次

发布时间：2019-06-06

本文共 1302 字，大约阅读时间需要 4 分钟。

正儿八经的树哈希的模板题。

哈希方法是求出每个儿子的哈希值，排序,末尾加上该点的size连成一个串，再对这个串哈希。

因为要求出A所有同构的树的hash值，直接hash的复杂度是n^n log

先随便指定一个根哈希一遍，再树dp换根即可，换根的时候把每个人父亲传过来的hash值也扔进串中，然后对每个人的串求前后缀，就可以方便地计算出它的hash值和它要传给每个儿子的hash值了。

然后对于B树要求去掉一个叶子的hash值，那么一个点传给它的叶子儿子的值就是一个合法的值，此外单独考虑一下根的父亲是叶子的情况即可。

//Achen#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             const int N=1e5+7,mod=998244353,bs=1011139;typedef long long LL;using namespace std;int n,tot,ans=-1;map
              
               mp;LL power[N],fh[N];template
               
                 void read(T &x) { char ch=getchar(); x=0; T f=1; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[N],nxt[N*2],to[N*2],sz[N],ha[N],f[N];void add(int u,int v) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;}bool cmp(const int &A,const int &B) { return ha[A]

v[N];void get_hash(int x) { int up=v[x].size(); ha[x]=0; sort(v[x].begin(),v[x].end(),cmp); for(int i=0;i

=0;i--) { if(v[x][i]!=n+2) { fh[v[x][i]]=((has*power[i]%mod+pr[i])%mod+(tot-sz[v[x][i]]))%mod; if(ecnt==2*n&&!nxt[fir[v[x][i]]]&&mp[fh[v[x][i]]]) if(ans==-1||v[x][i]

View Code

转载于:https://www.cnblogs.com/Achenchen/p/8390780.html

你可能感兴趣的文章