早上打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;
}