题解 JSOI2015 isomorphism

题解 JSOI2015 isomorphism

题面

BZOJ

个人体会

树Hash不会,自闭了.

解析

对于每棵树考虑找出它的所有重心再一波树Hash,

但是我们只把真节点当做一个节点.

然后直接判断相不相同就行了.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
#define ll long long
#define ull unsigned ll
#define filein(a) freopen(a".cpp","r",stdin)
#define fileout(a) freopen(a".cpp","w",stdout);
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

const int N=10005;
const int M=22;
const ull p=10491001;
int m;ull pw[N]={1};
vector<int> vec;
struct tree{
struct edge{int to,next;}e[N<<1];
int head[N],cnt,top;
int n,sum,d[N];
int sz[N],f[N],mn;
ull sta[N],h[N];
vector<ull> rt;
inline void add(int x,int y){
e[++cnt]=(edge){head[x],y};head[x]=cnt;
}
inline void init(){
memset(d,0,sizeof(d));cnt=0;
memset(head,0,sizeof(head));
}
inline void get_root(int x,int fa){
sz[x]=(d[x]!=2);f[x]=0;
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(k==fa) continue;
get_root(k,x);
sz[x]+=sz[k];f[x]=max(f[x],sz[k]);
}
f[x]=max(f[x],sum-sz[x]);mn=min(mn,f[x]);
}
inline void get_hash(int x,int fa){
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(k!=fa) get_hash(k,x);
}
top=0;
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(k!=fa) sta[top++]=h[k];
}
sort(sta,sta+top);h[x]=top-1;
for(int i=0;i<top;i++) h[x]+=pw[i]*sta[i];
}
inline void work(){
n=read();mn=0x3f3f3f3f;
for(int i=1;i<n;i++){
int x=read(),y=read();
add(x,y);add(y,x);
d[x]++;d[y]++;
}
for(int i=1;i<=n;i++) sum+=(d[i]!=2);
get_root(1,0);
for(int i=1;i<=n;i++)
if(f[i]==mn) get_hash(i,0),rt.push_back(h[i]);
}
}t[M];

inline bool cmp(int x,int y){return t[x].sum<t[y].sum;}

inline bool check(int x,int y){
for(int i=0,mx1=t[x].rt.size();i<mx1;i++){
for(int j=0,mx2=t[y].rt.size();j<mx2;j++){
if(t[x].rt[i]==t[y].rt[j]) return 1;
}
}
return 0;
}

int main(){
m=read();
for(int i=1;i<N;i++) pw[i]=pw[i-1]*p;
for(int i=1;i<=m;i++) t[i].work();
for(int i=1;i<=m;i++){
int flag=1;
for(int j=0,mx=vec.size();j<mx;j++)
if(check(i,vec[j])){flag=0;break;}
if(flag) vec.push_back(i);
}
sort(vec.begin(),vec.end(),cmp);
printf("%d\n",vec.size());
for(int i=0,mx=vec.size();i<mx;i++)
printf("%d ",t[vec[i]].sum);
return 0;
}
感谢您又打赏