求助凌晨CF E
  • 板块学术版
  • 楼主Lgx_Q
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/5 11:15
  • 上次更新2023/10/23 23:00:33
查看原帖
求助凌晨CF E
375953
Lgx_Q楼主2023/3/5 11:15

早上打vp,E 题 WA on test 14

是哈希问题吗?请奆佬指教

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=6e5+10;
const unsigned ll b0=152763,b1=1e9+7;
ll n,x,a[maxn],u,v,head[maxn],tot,ans;
unsigned ll d[maxn][2],f[maxn][2],H0,H1;
map<pair<unsigned ll,unsigned ll>,ll>mp;
struct edge
{
	ll v,nxt;
}e[maxn];
void insert(ll u,ll v)
{
	e[++tot]=(edge){v,head[u]};
	head[u]=tot;
}
void dfs1(ll u,ll fa)
{
	d[u][0]=d[u][1]=1;
	for(ll i=head[u];i;i=e[i].nxt)
	{
		ll v=e[i].v;
		if(v!=fa)
		{
			dfs1(v,u);
			d[u][0]+=d[v][0]*b0;
			d[u][1]+=d[v][1]*b1;
		}
	}
}
void dfs2(ll u,ll fa)
{
	for(ll i=head[u];i;i=e[i].nxt)
	{
		ll v=e[i].v;
		if(v!=fa)
		{
			f[v][0]=(f[u][0]+(d[u][0]-d[v][0]*b0))*b0;
			f[v][1]=(f[u][1]+(d[u][1]-d[v][1]*b1))*b1;
			dfs2(v,u);
		}
	}
	f[u][0]+=d[u][0];
	f[u][1]+=d[u][1];
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<n;i++)
	{
		scanf("%lld",&x);
		++a[x];
	}
	unsigned ll v0=1,v1=1;
	for(ll i=0;i<n;i++,v0*=b0,v1*=b1)
	{
		H0+=a[i]*v0;
		H1+=a[i]*v1;
	}
	v0=1, v1=1;
	for(ll i=0;i<n;i++,v0*=b0,v1*=b1) mp[make_pair(H0+v0,H1+v1)]=1;
	for(ll i=1;i<n;i++)
	{
		scanf("%lld%lld",&u,&v);
		insert(u,v);
		insert(v,u);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(ll i=1;i<=n;i++)
		if(mp.count(make_pair(f[i][0],f[i][1]))) ++ans;
	printf("%lld\n",ans);
	for(ll i=1;i<=n;i++)
		if(mp.count(make_pair(f[i][0],f[i][1])))
			printf("%lld ",i);
	return 0;
}
2023/3/5 11:15
加载中...