From 0b921dd3951c30d7fe008de00c9e2bbc8c4cc3c5 Mon Sep 17 00:00:00 2001
From: XLor <yjl9903@vip.qq.com>
Date: Tue, 13 Aug 2019 20:08:42 +0800
Subject: [PATCH] Update tree-hash.md

---
 docs/graph/tree-hash.md | 247 +++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 233 insertions(+), 14 deletions(-)

diff --git a/docs/graph/tree-hash.md b/docs/graph/tree-hash.md
index 9d3bdb20..147dedbd 100644
--- a/docs/graph/tree-hash.md
+++ b/docs/graph/tree-hash.md
@@ -12,16 +12,22 @@ $$
 
 #### Notes
 
-其中 $f_x$ 为以节点 $x$ 为根的子树对应的哈希值。特殊地，我们令叶子节点的哈希值为 $1$ 。
+其中 $f_x$ 为以结点 $x$ 为根的子树对应的哈希值。特殊地，我们令叶子结点的哈希值为 $1$ 。
 
- $size_{x}$ 表示以节点 $x$ 为根的子树大小。
+ $size_{x}$ 表示以结点 $x$ 为根的子树大小。
 
- $son_{x,i}$ 表示 $x$ 所有子节点以 $f$ 作为关键字排序后排名第 $i$ 的儿子。
+ $son_{x,i}$ 表示 $x$ 所有子结点以 $f$ 作为关键字排序后排名第 $i$ 的儿子。
 
  $seed$ 为选定的一个合适的种子（最好是质数，对字符串 hash 有了解的人一定不陌生）
 
 上述哈希过程中，可以适当取模避免溢出或加快运行速度。
 
+#### Hack
+
+![treehash1](./images/treehash1.png)
+
+上图中，可以计算出两棵树的哈希值均为 $60(1+seed)$。
+
 ## Method II
 
 ### Formula
@@ -32,31 +38,51 @@ $$
 
 #### Notes
 
-其中 $f_x$ 为以节点 $x$ 为根的子树对应的哈希值。特殊地，我们令叶子节点的哈希值为 $1$ 。
+其中 $f_x$ 为以结点 $x$ 为根的子树对应的哈希值。特殊地，我们令叶子结点的哈希值为 $1$ 。
 
- $size_{x}$ 表示以节点 $x$ 为根的子树大小。
+ $size_{x}$ 表示以结点 $x$ 为根的子树大小。
 
- $son_{x,i}$ 表示 $x$ 所有子节点之一（不用排序）。
+ $son_{x,i}$ 表示 $x$ 所有子结点之一（不用排序）。
 
  $seed$ 为选定的一个合适的质数。
 
  $\large\bigoplus$ 表示异或和。
 
-## Example
+#### Hack
+
+由于异或的性质，如果一个结点下有多棵本质相同的子树，这种哈希值将无法分辨该种子树出现 $1,3,5,\dots$ 次的情况。
+
+## Method III
+
+### Formula
+
+$$
+f_{now}=1+\sum f_{son_{now,i}} \times prime(size_{son_{now,i}})
+$$
+
+### Notes
 
-### Problem
+其中 $f_x$ 为以结点 $x$ 为根的子树对应的哈希值。
 
- [Luogu P5403](https://www.luogu.org/problemnew/show/P5043) 
+ $size_{x}$ 表示以结点 $x$ 为根的子树大小。
 
-### Solution
+ $son_{x,i}$ 表示 $x$ 所有子结点之一（不用排序）。
 
-我们用上述方式任选其一进行哈希，注意到我们求得的是子树的 hash 值，也就是说只有当根一样时同构的两棵子树 hash 值才相同。由于数据范围较小，我们可以暴力求出以每个点为根时的哈希值，排序后比较。
+ $prime(i)$ 表示第 $i$ 个质数。
+
+主要参考了该篇博客 [树hash](https://www.cnblogs.com/huyufeifei/p/10817673.html)。
+
+## Example
+
+### Problem [「BJOI2015」树的同构](https://www.luogu.org/problemnew/show/P5043)
+
+我们用上述方式任选其一进行哈希，注意到我们求得的是子树的 hash 值，也就是说只有当根一样时同构的两棵子树 hash 值才相同。由于数据范围较小，我们可以暴力求出以每个点为根时的哈希值，也可以通过 up and down 树形 dp 的方式，遍历树两遍求出以每个点为根时的哈希值，排序后比较。
 
 如果数据范围较大，我们可以通过找重心的方式来优化复杂度。（一棵树的重心最多只有两个，分别比较即可）
 
-### Code
+#### Code
 
-#### Method I
+##### Method I
 
 ??? "例题参考代码"
     ```cpp
@@ -184,7 +210,7 @@ $$
     }
     ```
 
-#### Method II
+##### Method II
 
 ??? "例题参考代码"
     ```cpp
@@ -290,6 +316,199 @@ $$
     int main() {}
     ```
 
+### Problem [HDu 6647](http://acm.hdu.edu.cn/showproblem.php?pid=6647)
+
+题目要求的是遍历一棵无根树产生的本质不同括号序列方案数。
+
+首先，注意到一个结论，对于两棵有根树，如果他们不同构，一定不会生成相同的括号序列。我们先考虑遍历有根树能够产生的本质不同括号序列方案数，假设我们当前考虑的子树根结点为 $u$，记 $f(u)$ 表示这棵子树的方案数，$son(u)$ 表示 $u$ 的儿子结点集合，从 $u$ 开始往下遍历，顺序可以随意选择，产生 $|son(u)|!$ 种排列，遍历每个儿子结点 $v$，$v$ 的子树内有 $f(v)$ 种方案，因此有 $f(u)=|son(u)|! \cdot \prod_{v\in son(u)} f(v)$。但是，同构的子树之间会产生重复，$f(u)$ 需要除掉每种本质不同子树出现次数阶乘的乘积，类似于多重集合的排列。
+
+通过上述树形 dp，可以求出根结点的方案数，再通过 up and down 树形 dp，将父亲结点的哈希值和方案信息转移给儿子，可以求出以每个结点为根时的哈希值和方案数，每种不同的子树只需要计数一次即可。
+
+注意，本题数据较强，树哈希很容易发生冲突。这里提供一个比较简单的解决方法，求出一个结点子树的哈希值后，可以将其前后分别插入一个值再计算一遍哈希值。
+
+#### Code
+
+??? "例题参考代码"
+    ```cpp
+    #include <iostream>
+    #include <cstdio>
+    #include <cstring>
+    #include <cmath>
+    #include <algorithm>
+    #include <vector>
+    #include <utility>
+    #include <set>
+    #include <map>
+    using namespace std;
+    typedef long long ll;
+    typedef unsigned long long ull;
+    typedef pair<int,int> PII;
+    const int mod = 998244353;
+    const int inf = 1 << 30;
+    const int maxn = 100000 + 5;
+
+    namespace sieve{
+        const int maxp = 2000000 + 5;
+        int vis[maxp], prime[maxp], tot;
+        void init() {
+            ms(vis, 0);
+            for (int i = 2; i < maxp; i++) {
+                if (!vis[i]) prime[++tot] = i;
+                for (int j = 1; j <= tot && prime[j] * i < maxp; j++) {
+                    vis[i * prime[j]] = 1;
+                    if (i % prime[j] == 0) break;
+                }
+            }
+        }
+    }
+    namespace MyIO {
+        struct fastIO {
+            char s[100000]; int it,len;
+            fastIO() { it = len = 0; }
+            inline char get() {
+                if (it < len) return s[it++];
+                it = 0; len = fread(s, 1, 100000, stdin);
+                if (len == 0) return EOF;
+                else return s[it++];
+            }
+            bool notend() {
+                char c = get();
+                while(c == ' ' || c == '\n') c = get();
+                if (it > 0) it--;
+                return c != EOF;
+            }
+        } buff;
+        inline int gi() {
+            int r = 0; bool ng = 0; 
+            char c = buff.get();
+            while (c != '-' && (c < '0' || c > '9')) c = buff.get();
+            if (c == '-') ng = 1, c = buff.get();
+            while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = buff.get();
+            return ng ? -r : r;
+        }
+    }
+    namespace {
+        inline int add(int x, int y) {
+            x += y;
+            return x >= mod ? x -= mod : x;
+        }
+        inline int sub(int x, int y) {
+            x -= y;
+            return x < 0 ? x += mod : x;
+        }
+        inline int mul(int x, int y) {
+            return 1ll * x * y % mod;
+        }
+        inline int qpow(int x, ll n) {
+            int r = 1;
+            while (n > 0) {
+                if (n & 1) r = 1ll * r * x % mod;
+                n >>= 1; x = 1ll * x * x % mod;
+            }
+            return r;
+        }
+        inline int inv(int x) {
+            return qpow(x, mod - 2);
+        }
+    }
+    using sieve::prime;
+    using MyIO::gi;
+    
+    int ping[maxn], pingv[maxn];
+    
+    int n, ans, siz[maxn];
+    vector<int> edge[maxn];
+    map<ull,int> uqc[maxn];
+    map<ull,int>::iterator it;
+    
+    ull hashval[maxn], hashrt[maxn];
+    ull srchashval[maxn], srchashrt[maxn];
+    int dp[maxn], rdp[maxn];
+    ull pack(ull val, int sz) {
+        return 2ull + 3ull * val + 7ull * prime[sz + 1];
+    }
+    void predfs(int u, int ff) {
+        siz[u] = dp[u] = 1;
+        hashval[u] = 1;
+        int sz = 0;
+        for (int v: edge[u]) {
+            if (v == ff) continue;
+            predfs(v, u);
+            sz++;
+            siz[u] += siz[v];
+            dp[u] = mul(dp[u], dp[v]);
+            uqc[u][hashval[v]]++;
+            hashval[u] += hashval[v] * prime[siz[v]];
+        }
+    
+        srchashval[u] = hashval[u];
+        hashval[u] = pack(hashval[u], siz[u]);
+    
+        dp[u] = mul(dp[u], ping[sz]);
+        for (it = uqc[u].begin(); it != uqc[u].end(); it++) {
+            dp[u] = mul(dp[u], pingv[it->second]);
+        }
+    }
+    set<ull> qc;
+    void dfs(int u, int ff) {
+        if (!qc.count(hashrt[u])) {
+            qc.insert(hashrt[u]);
+            ans = add(ans, rdp[u]);
+        }
+        for (int v: edge[u]) {
+            if (v == ff) continue;
+    
+            ull tmp = srchashrt[u] - hashval[v] * prime[siz[v]];
+            tmp = pack(tmp, n - siz[v]);
+    
+            uqc[v][tmp]++;
+            srchashrt[v] = srchashval[v] + tmp * prime[n - siz[v]];
+            hashrt[v] = pack(srchashrt[v], n);
+    
+            int tdp = mul(rdp[u], inv(dp[v]));
+            tdp = mul(tdp, inv((int)edge[u].size()));
+            tdp = mul(tdp, uqc[u][hashval[v]]);
+            rdp[v] = mul(dp[v], tdp);
+            rdp[v] = mul(rdp[v], (int)edge[v].size());
+            rdp[v] = mul(rdp[v], inv(uqc[v][tmp]));
+    
+            dfs(v, u);
+        }
+    }
+    
+    int main() {
+        sieve::init(); ping[0] = pingv[0] = 1;
+        for (int i = 1; i < maxn; i++) {
+            ping[i] = mul(ping[i - 1], i);
+            pingv[i] = mul(pingv[i - 1], inv(i));
+        }
+        int T = gi();
+        while (T--) {
+            n = gi();
+            for (int i = 2, u, v; i <= n; i++) {
+                u = gi(); v = gi();
+                edge[u].push_back(v);
+                edge[v].push_back(u);
+            }
+    
+            predfs(1, 0);
+            ans = 0; qc.clear();
+            rdp[1] = dp[1]; 
+            hashrt[1] = hashval[1];
+            srchashrt[1] = srchashval[1];
+            dfs(1, 0);
+    
+            printf("%d\n", ans);
+    
+            for (int i = 1; i <= n; i++) {
+                edge[i].clear();
+                uqc[i].clear();
+            }
+        }
+        return 0;
+    }
+    ```
+
 ## At Last
 
 事实上，树哈希是可以很灵活的，可以有各种各样奇怪的姿势来进行 hash，只需保证充分性与必要性，选手完全可以设计出与上述方式不同的 hash 方式。
-- 
2.11.0