题解 P6084 【[JSOI2015]isomorphism】
Great_Influence
2020-02-11 22:31:26
这道题可以分成两部分。
1. 缩树。
2. 树同构。
第一步直接在原树上重新建树即可，关键在于第二步。
这里的主要问题在于对无根树判同构很麻烦，因此我们可以考虑直接将无根树转换成有根树。
至于选什么点做根， 这个就很明显了：重心。
唯一的问题在于一棵树的重心可能有两个。不过这两个重心肯定是直接相连的，我们把相连的边断开看做两棵树即可。
然后跑你最喜欢的有根树哈希算法就可以了。我这里选择的哈希值计算方法是:
$$Hash[u]=\oplus(Hash[v]-W[u])*W[v]$$
其中 $W[u]$ 是随机出来的某种系数。
代码:
```cpp
#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mp make_pair
using namespace std;
inline void Chkmax(int&u,int v){u<v?u=v:0;}
const int MAXN = 1e4 + 7;
vector <int> ed[MAXN];
set < pair<int, unsigned long long> > G;
static int rt1, rt2, d[MAXN];
static int sz[MAXN], F[MAXN];
static unsigned long long w[MAXN];
void getcentr(int u, int fa, int al)
{
sz[u] = 1, F[u] = 0;
for(int v : ed[u]) if(v ^ fa) getcentr(v, u, al), Chkmax(F[u], sz[v]), sz[u] += sz[v];
Chkmax(F[u], al - sz[u]);
if(!rt1 || F[u] < F[rt1]) rt1 = u, rt2 = fa;
}
static unsigned long long hs[MAXN];
void geths(int u, int fa)
{
sz[u] = 1;
hs[u] = 0;
for(int v : ed[u]) if(v ^ fa) geths(v, u), sz[u] += sz[v];
for(int v : ed[u]) if(v ^ fa)
hs[u] ^= (hs[v] - w[sz[u]]) * w[sz[v]];
hs[u] ^= w[sz[u]];
}
inline unsigned long long calc(int n, int zz)
{
rt1 = rt2 = 0;
Rep(i, 1, n) if(d[i] == 1) {getcentr(i, 0, zz); break;}
//cerr << rt1 << ' ' << rt2 <<endl;
if(F[rt1] == F[rt2])
{
geths(rt1, rt2), geths(rt2, rt1);
return hs[rt1] ^ hs[rt2];
}
geths(rt1, 0);
return hs[rt1];
}
static vector <int> us[MAXN];
static pair <int, int> cn[MAXN];
void shrink(int u, int fa, int tf, int & n)
{
if(d[u] == 2) {for(int v : us[u]) if(v ^ fa) shrink(v, u, tf, -- n);}
else
{
if(tf) ed[u].pb(tf), ed[tf].pb(u);
for(int v : us[u]) if(v ^ fa) shrink(v, u, u, n);
}
}
#define read(x) cin>>x
inline void init()
{
static int n, m, u, v;
srand(time(NULL));
Rep(i, 1, 10000) w[i] = rand() | (unsigned long long)rand() << 30;
read(m);
Rep(i, 1, m)
{
read(n);
Rep(i, 1, n) us[i].resize(0), ed[i].resize(0), d[i] = 0;
Rep(i, 1, n - 1) read(u), read(v), ++ d[u], ++ d[v], us[u].pb(v), us[v].pb(u);
int s = n;
Rep(i, 1, n) if(d[i] == 1) {shrink(i, 0, 0, s); break;}
G.insert(mp(s, calc(n, s)));
}
}
inline void solve()
{
cout << G.size() << endl;
for(auto z : G) printf("%d ", z.first);
puts("");
}
int main()
{
init();
solve();
return 0;
}
```