Luogu

分析

判无根树重构时,先以重心为根转为有根树,再做树哈希。

这道题稍微改一下,求重心时忽略假节点,然后设计一种假节点的哈希值等于它的儿子的哈希值的树哈希方式就好了。

需要注意的是无根树可能有两个重心。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef unsigned long long ull;
 
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10,M=20+5;
const ull BASE=19491001;

ull pw[N];

namespace solver {
    int n;
    
    struct edge { int v,nxt; } e[N<<1];
    int head[N],deg[N],cnt=0;
    inline void addEdge(int u,int v) {
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
    }

    int sumsz,minf,sz[N],f[N]; ull h[N],v[N]; int top;
    inline void getroot(int u,int fa) {
        sz[u]=deg[u]!=2,f[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==fa) continue;
            getroot(v,u); sz[u]+=sz[v],f[u]=max(f[u],sz[v]);
        }
        f[u]=max(f[u],sumsz-sz[u]); minf=min(minf,f[u]);
    }
    inline void gethash(int u,int fa) {
        for (re int i=head[u];i;i=e[i].nxt)
            if (e[i].v!=fa) gethash(e[i].v,u);
        top=0;
        for (re int i=head[u];i;i=e[i].nxt)
            if (e[i].v!=fa) v[top++]=h[e[i].v];
        sort(v,v+top); h[u]=top-1;
        for (re int i=0;i<top;++i) h[u]+=pw[i]*v[i];
    }

    vector<ull> H;
    inline void work() {
        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read();
            addEdge(u,v),++deg[u];
            addEdge(v,u),++deg[v];
        }
        sumsz=0;
        for (re int i=1;i<=n;++i) if (deg[i]!=2) ++sumsz;
        minf=2e9,getroot(1,0); H.clear();
        for (re int i=1;i<=n;++i)
            if (f[i]==minf) gethash(i,0),H.push_back(h[i]);
    }

    inline void init() {
        cnt=0,memset(head,0,sizeof(head)),memset(deg,0,sizeof(deg));
    }
}

vector<ull> H[M]; int sz[M];

inline int check(int x,int y) {
    for (re int i=0;i<H[x].size();++i)
        for (re int j=0;j<H[y].size();++j)
            if (H[x][i]==H[y][j]) return 1;
    return 0;
}

vector<int> vec;
inline int cmp(int x,int y) { return sz[x]<sz[y]; }
int main() {
    pw[0]=1; for (re int i=1;i<N;++i) pw[i]=pw[i-1]*BASE;
    int m=read();
    for (re int i=1;i<=m;++i) {
        solver::init(),solver::work();
        H[i]=solver::H,sz[i]=solver::sumsz;
    }
    for (re int i=1;i<=m;++i) {
        int flag=1;
        for (re int j=0;j<vec.size();++j)
            if (check(i,vec[j])) { flag=0; break; }
        if (flag) vec.push_back(i);
    }
    sort(vec.begin(),vec.end(),cmp);
    printf("%u\n",vec.size());
    for (re int i=0;i<vec.size();++i) printf("%d ",sz[vec[i]]);
    puts("");
    return 0;
}
最后修改:2020 年 02 月 27 日 09 : 27 AM