社区讨论

求助,找不出问题了

P5043【模板】树同构 / [BJOI2015] 树的同构参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi7x32ya
此快照首次捕获于
2025/11/21 05:02
4 个月前
此快照最后确认于
2025/11/21 05:02
4 个月前
查看原帖
哈希公式是这样的
fnow=sizenow×fsonnow,i×basi1f_{now}=size_{now} \times \sum f_{son_{now,i}}\times bas^{i-1}
每次只比较两个重心。
CPP
#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int N=110;
const ull bas=19260817;

struct Edge
{
    int to,nxt;

    Edge(){}
    Edge(int to,int nxt):to(to),nxt(nxt){}
}e[N*2];
int head[N],cnt;

void addedge(int u,int v)
{
    e[++cnt]=Edge(v,head[u]);
    head[u]=cnt;
}

vector<int>child[N];

int root;
int maxp,tot;
int siz[N];
ull f[N];

void FindG(int now,int fa)
{
    siz[now]=1;
    int maxsiz=0;
    for(int i=head[now];i;i=e[i].nxt)
    {
        int vs=e[i].to;
        if(vs==fa) continue;
        FindG(vs,now);
        siz[now]+=siz[vs];
        maxsiz=max(maxsiz,siz[vs]);
    }
    maxsiz=max(maxsiz,tot-siz[now]);
    if(maxsiz<maxp)
    {
        maxp=maxsiz;
        root=now;
    }
}

void dfs(int now,int fa)
{
    for(int i=head[now];i;i=e[i].nxt)
    {
        int vs=e[i].to;
        if(vs==fa) continue;
        dfs(vs,now);
        child[now].push_back(vs);
    }
    sort(child[now].begin(),child[now].end(),[](const int &a,const int &b)->bool {
        return f[a]<f[b];
    });
    ull B=1;
    for(auto son:child[now])
    {
        f[now]+=f[son]*B;
        B*=bas;
    }
    f[now]*=siz[now];
    if(!f[now]) f[now]=1;
}

map<ull,int>mp;

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>tot;
        memset(head,0,sizeof(head));
        cnt=0;
        for(int j=1;j<=tot;j++)
        {
            int tmp;
            cin>>tmp;
            if(tmp) 
            {
                addedge(tmp,j);
                addedge(j,tmp);
            }
        }

        maxp=0x3f3f3f3f;
        memset(f,0,sizeof(f));        
        FindG(tot,0);
        for(int i=1;i<=tot;i++) child[i].clear();
        dfs(root,0);
        if(mp[f[root]])
        {
            cout<<mp[f[root]]<<'\n';
            continue;
        }
        maxp=0x3f3f3f3f;
        FindG(root,0);
        memset(f,0,sizeof(f));
        for(int i=1;i<=tot;i++) child[i].clear();
        dfs(root,0);
        if(!mp[f[root]])
        {
            mp[f[root]]=i;
        }
        cout<<mp[f[root]]<<'\n';
    }
}

回复

0 条回复,欢迎继续交流。

正在加载回复...