【HYSBZOJ】【哈希】【换根DP】4754 [Jsoi2016]独特的树叶

HYSBZOJ 4754 [Jsoi2016]独特的树叶

题目大意

◇题目传送门◆

分析

这道题显然考察的是树哈希。

我这里采用的方法是：

$$f(u)=1+\sum _{v\in son(u)}f(v)\times P_{si{z}_v}$$

其中$P$表示质数序列，$si{z}_v$表示以$v$为根的子树的大小，$f(u)$表示以$u$为根的子树的哈希值。

现在的要求就是对于$A$和$B$中的每个节点，求出以该节点为根的整棵树的哈希值。

这样的话，我们考虑换根。

设$g(u)$为去掉$u$这棵子树后的整棵树的哈希值，不难得出：

$$g(u)=h(u)?f(u)\times P_{si{z}_u}$$

其中$h(u)$表示以当前节点为根，整棵树的哈希值。$h(u)$的表达式我们也不难得出：

$$h(u)=\{\begin{array}{ll}f(u)& u=1\\ f(u)+g(u)\times P_{si{z}_1?si{z}_u}& u?=1\end{array}$$

这里我用节点$1$为根。

然后我们将$B$的所有哈希值塞进set或者map里面去。再枚举$A$中的每一个点，将它接到一个虚拟的点上面去，算出新的哈希值$1+h(u)\times P_N$，找到最小的那个节点就是了。

总时间复杂度为$O(N\log N)$。

参考代码

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;typedef unsigned long long ull;
const int Maxn = 1e5;
const int P = 1e7;ull SEED[Maxn + 5];
void calcSEED() {
    static bool ispri[P + 5];int cnt = 0;for(int i = 2; i <= P; i++) {
    if(!ispri[i])SEED[++cnt] = i;for(int j = 1; i * SEED[j] <= P && j <= cnt; j++) {
    ispri[i * SEED[j]] = true;if(i % SEED[j] == 0) break;}}
}struct Graph {
    struct Edge {
    int to;Edge *nxt;};Edge pool[Maxn * 2 + 5];Edge *G[Maxn + 5], *ecnt;void init() {
    memset(G, 0, sizeof G);ecnt = &pool[0];}void addedge(int u, int v) {
    Edge *p = ++ecnt;p->to = v, p->nxt = G[u];G[u] = p;}ull hashval[Maxn + 5];ull f[Maxn + 5], g[Maxn + 5];int siz[Maxn + 5];void dfs1(int u, int fa) {
    f[u] = siz[u] = 1; for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;if(v == fa) continue;dfs1(v, u);siz[u] += siz[v], f[u] += SEED[siz[v]] * f[v];}}void dfs2(int u, int fa) {
    if(fa != 0) g[u] = hashval[fa] - f[u] * SEED[siz[u]];if(fa == 0) hashval[u] = f[u];else hashval[u] = f[u] + g[u] * SEED[siz[1] - siz[u]];for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;if(v == fa) continue;dfs2(v, u);}}void calc_hash() {
    dfs1(1, 0);dfs2(1, 0);}
};int N;Graph A, B;
map<ull, int> s;
int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifcalcSEED();A.init(), B.init();scanf("%d", &N);for(int i = 1; i < N; i++) {
    int u, v;scanf("%d %d", &u, &v);A.addedge(u, v), A.addedge(v, u);}for(int i = 1; i <= N; i++) {
    int u, v;scanf("%d %d", &u, &v);B.addedge(u, v), B.addedge(v, u);}A.calc_hash(), B.calc_hash();for(int i = 1; i <= N + 1; i++)if(!s.count(B.hashval[i])) s[B.hashval[i]] = i;else s[B.hashval[i]] = min(s[B.hashval[i]], i);for(int i = 1; i <= N; i++)if(s.count(1 + A.hashval[i] * SEED[N])) {
    printf("%d\n", s[1 + A.hashval[i] * SEED[N]]);break;}return 0;
}