题解 P4323 【[JSOI2016]独特的树叶】

RabbitHu

2018-06-11 10:04:31

Solution

> 本文同步发布于[胡小兔的博客](https://www.cnblogs.com/RabbitHu/p/9165770.html),欢迎交流 >v< 这道题是一道判断无根树同构的模板题,判断同构主要的思路就是哈希。 一遇到哈希题,一百个人能有一百零一种哈希方式,这篇题解随便选用了一种——类似[杨弋《Hash在信息学竞赛中的一类应用》](https://wenku.baidu.com/view/72d3d14f852458fb770b560d.html)中的这种,可能不是最简洁好写的,但是能用。 我的哈希规则:子树$u$的哈希值由它的每一个子树$v_i$的哈希值得来,首先将所有$f(v)$排个序(防止顺序不同造成影响),然后$f(u) = size(u) * \sum_i f(v_i)W^{i - 1} \bmod P$,$W$是事先选取的一个位权,$P$是模数,$size(u)$是子树$u$的大小。 这样DFS一遍可求出以$1$号节点为根时,所有子树的哈希值$f(u)$。 但是这是无根树,我们想求出以任意节点为根时整棵树的哈希值。 设$fa_u$为以$1$为根时$u$的父亲,则上面的$f(u)$也是以$fa_u$为根时子树$u$的哈希值。 再求一个$g(u)$表示以$u$为根时子树$fa_u$的哈希值。这个$g(u)$怎么求呢?再DFS一遍,对于每个节点,$g(u)$由$g(fa_u)$以及$u$的每个兄弟$v_i$的$f(v_i)$得来。但是直接暴力枚举的话在菊花图上是$O(n^2)$的,那怎么办呢? 对于每个节点$u$维护一个数组,存储它所有儿子的哈希值$f(v)$,如果有父亲,则$g(u)$也在里面,把这个数组排好序,求出每个前缀的哈希值和每个后缀的哈希值。这时,以$u$为根时整棵树的哈希值就是整个数组的哈希值(再乘上子树大小$n$)。 此时求每个儿子$v$的$g(v)$,就是从那个数组中间去掉$f(v)$后的哈希值,二分查找后把前缀哈希值和后缀哈希值拼起来就可以得到。记得乘上$v$为根时$u$的$size$即$n - size(v)$。 这样就求出以每个节点为根的哈希值了。 把A的所有哈希值存到一个set里,然后枚举B的每个度为1的点$u$,求出以$u$为根它的唯一子树$v$的哈希值,如果set里有这个值,$u$就是所求的点之一。 代码比较丑,见谅 >< ```cpp #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <iostream> #include <vector> #include <set> #define space putchar(' ') #define enter putchar('\n') typedef long long ll; using namespace std; template <class T> void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 100005, W = 1000000021, P = 999999137; int n, m, fa[N], f[N], g[N], pw[N], Sze[N], deg[N], ans = P; int ecnt, adj[N], nxt[2*N], go[2*N]; vector <int> son[N], sl[N], sr[N]; set <int> vis; bool isB; void add(int u, int v){ if(isB) deg[u]++; go[++ecnt] = v; nxt[ecnt] = adj[u]; adj[u] = ecnt; } int dfs1(int u, int pre){ Sze[u] = 1; fa[u] = pre; son[u].clear(); for(int e = adj[u], v; e; e = nxt[e]) if((v = go[e]) != pre){ son[u].push_back(dfs1(v, u)); Sze[u] += Sze[v]; } if(son[u].empty()) return f[u] = 1; sort(son[u].begin(), son[u].end()); ll ret = 0; for(int i = 0; i < (int)son[u].size(); i++) ret = (ret * W + son[u][i]) % P; return f[u] = Sze[u] * ret % P; } void dfs2(int u){ if(fa[u]){ son[u].push_back(g[u]); sort(son[u].begin(), son[u].end()); } int sze = son[u].size(); sl[u].resize(sze); sl[u][0] = son[u][0]; for(int i = 1; i < sze; i++) sl[u][i] = ((ll)sl[u][i - 1] * W + son[u][i]) % P; sr[u].resize(sze); sr[u][sze - 1] = son[u][sze - 1]; for(int i = sze - 2; i >= 0; i--) sr[u][i] = (sr[u][i + 1] + (ll)son[u][i] * pw[sze - i - 1]) % P; for(int e = adj[u], v; e; e = nxt[e]) if((v = go[e]) != fa[u]){ if(sze == 1){ g[v] = 1; dfs2(v); break; } int p = lower_bound(son[u].begin(), son[u].end(), f[v]) - son[u].begin(); g[v] = 0; if(p + 1 < sze) g[v] = sr[u][p + 1]; if(p - 1 >= 0) g[v] = (g[v] + (ll)sl[u][p - 1] * pw[sze - 1 - p]) % P; g[v] = (ll)g[v] * (n - Sze[v]) % P; if(isB && deg[v] == 1 && vis.find(g[v]) != vis.end()) ans = min(ans, v); dfs2(v); } if(!isB) vis.insert((ll)sl[u][sze - 1] * n % P); } int main(){ pw[0] = 1; for(int i = 1; i < N; i++) pw[i] = (ll)pw[i - 1] * W % P; read(n); for(int i = 1, u, v; i < n; i++) read(u), read(v), add(u, v), add(v, u); dfs1(1, 0); dfs2(1); ecnt = 0, isB = 1, n++; memset(adj, 0, sizeof(adj)); for(int i = 1, u, v; i < n; i++) read(u), read(v), add(u, v), add(v, u); dfs1(1, 0); if(deg[1] == 1 && vis.find(f[go[adj[1]]]) != vis.end()) ans = 1; dfs2(1); write(ans), enter; return 0; } ```