P6204 [USACO07CHN] Treasure G 题解

· · 题解

省流题意

给定一棵基环树，求以每个节点为根时共有多少种不同构的树。

题目分析

如果这是一颗树的话，那么直接树哈希，换根 DP 即可，在此不再赘述，详见板子题。

现在我们需要考虑的是如何将这个环也哈希进来。这时我们发现，环与孩子的唯一区别就是前者有序而后者无序，所以我们只需要采取字符串哈希的形式即可。又因为这是一个环，所以顺时针和逆时针没有区别，我们需要将两个方向上的哈希值相加。（rg[i] 代表环上的第 i 个点）

    ull now=0;
    for(int i=2;i<=cnt;i++)
        now=now*331+Hash[rg[i]];
    h[rg[1]]=now+Hash[rg[1]];
    for(int i=2;i<=cnt;i++){
        now-=Hash[rg[i]]*pow331[cnt-1];
        now=now*331+Hash[rg[i-1]];
        h[rg[i]]=now+Hash[rg[i]];
    }
    now=0;
    for(int i=cnt;i>=2;i--)
        now=now*331+Hash[rg[i]];
    h[rg[1]]+=now;
    for(int i=cnt;i>=2;i--){
        now-=Hash[rg[i]]*pow331[cnt-1];
        if(i==cnt)now=now*331+Hash[rg[1]];
        else now=now*331+Hash[rg[i+1]];
        h[rg[i]]+=now;
    }

这样就求出来了环上点的哈希值，其他的点正常求即可。

代码：

#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
    int f=1;x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+c-'0',c=getchar();
    x*=f,rd(args...);
}

typedef unsigned long long ull;
const ull mk=std::chrono::steady_clock::now().time_since_epoch().count();
ull Shift(ull x){x^=mk;x^=x<<13;x^=x>>7;x^=x<<17;x^=mk;return x;}
const int N=1e5+5;
int fst[N],nxt[N<<1],v[N<<1],idx,ans;
int n,vis[N],ring[N<<1],rg[N],deg[N],cnt;
inline void Add(int a,int b){
    v[idx]=b,nxt[idx]=fst[a];
    fst[a]=idx++;
}
int DFS(int x,int f){
    vis[x]=1;
    for(int i=fst[x];~i;i=nxt[i]){
        int y=v[i];
        if(y==f)continue;
        if(vis[y])return ring[i]=ring[i^1]=1,rg[++cnt]=y,1;
        if(DFS(y,x)){
            ring[i]=ring[i^1]=1;
            rg[++cnt]=y;
            if(rg[1]==x)return 0;
            return 1;
        }
    }
    return 0;
}
ull Hash[N],pow331[N],h[N];
set<ull> str,stt;
void Get_Hash(int x,int f){
    Hash[x]=h[x];
    for(int i=fst[x];~i;i=nxt[i]){
        int y=v[i];
        if(ring[i]||y==f)continue;
        Get_Hash(y,x);
        Hash[x]+=Shift(Hash[y]);
    }
}
inline void Solve_Ring(){
    pow331[1]=1;
    Get_Hash(rg[1],rg[1]);
    for(int i=2;i<=cnt;i++){
        Get_Hash(rg[i],rg[i]);
        pow331[i]=pow331[i-1]*331;
    }
    ull now=0;
    for(int i=2;i<=cnt;i++)
        now=now*331+Hash[rg[i]];
    h[rg[1]]=now+Hash[rg[1]];
    for(int i=2;i<=cnt;i++){
        now-=Hash[rg[i]]*pow331[cnt-1];
        now=now*331+Hash[rg[i-1]];
        h[rg[i]]=now+Hash[rg[i]];
    }
    now=0;
    for(int i=cnt;i>=2;i--)
        now=now*331+Hash[rg[i]];
    h[rg[1]]+=now;
    for(int i=cnt;i>=2;i--){
        now-=Hash[rg[i]]*pow331[cnt-1];
        if(i==cnt)now=now*331+Hash[rg[1]];
        else now=now*331+Hash[rg[i+1]];
        h[rg[i]]+=now;
    }
    for(int i=1;i<=cnt;i++)if(deg[rg[i]]<4)str.insert(h[rg[i]]);
    ans+=str.size();
}
void Get_Hashes(int x,int f){
    for(int i=fst[x];~i;i=nxt[i]){
        int y=v[i];
        if(ring[i]||y==f)continue;
        h[y]=Hash[y]+Shift(h[x]-Shift(Hash[y]));
        if(deg[y]<4)stt.insert(h[y]);
        Get_Hashes(y,x);
    }
}
inline void Solve_Tree(){
    for(int i=1;i<=cnt;i++){
        Get_Hash(rg[i],rg[i]);
        Get_Hashes(rg[i],rg[i]);
    }
    ans+=stt.size();
}
int main(){
    memset(fst,-1,sizeof fst);
    rd(n);
    for(int i=1;i<=n;i++){
        h[i]=1;
        int x,y;rd(x,y);
        Add(x,y);Add(y,x);
        deg[y]++,deg[x]++;
    }
    DFS(1,1);
    Solve_Ring();
    Solve_Tree();
    printf("%d\n",ans);
    return 0;
}