社区讨论
求助,找不出问题了
P5043【模板】树同构 / [BJOI2015] 树的同构参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi7x32ya
- 此快照首次捕获于
- 2025/11/21 05:02 4 个月前
- 此快照最后确认于
- 2025/11/21 05:02 4 个月前
哈希公式是这样的
每次只比较两个重心。
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 条回复,欢迎继续交流。
正在加载回复...