(https://codeforces.com/contest/1800/problem/G)
题目如下：
大意是：给定一颗以1为根节点的树，然后判断这棵树是不是对称的。这里使用AHU算法进行树哈希，在递归的时候对每一个子节点为根的子树求出一个编号，然后在map里面记录。通过判断子树的编号是否一样来判断子树是否同构。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 void solve() 5 { 6 int curr_size = 0; 7 //get_index在这里的作用是对每一种结构的子树做一个离散化，映射成一个数字下标 8 map<vector<int>, int> get_index; 9 //存储一种子树结构对应的一个数字下标是否是对称的 10 map<int, bool> is_symmetrical; 11 12 //dfs函数的目标是求出以node为根节点的子树的编号 13 auto dfs = [&](auto self, int node, int father, vector<vector<int>> &list_node) -> int { 14 vector<int> children; 15 for (auto &child : list_node[node]) { 16 //递归的加入所有子节点编号 17 if (child != father) { 18 children.emplace_back(self(self, child, node, list_node)); 19 } 20 } 21 //排序是为了保证子树结构的唯一性，这样在加入map的时候才不会出错 22 sort(children.begin(), children.end()); 23 24 //如果没有统计过这个编号，那么就统计进去 25 if (!get_index.count(children)) { 26 //判断对称性，出现奇数次的子树不超过1个，并且是对称的，那么就认为这个父节点是对称的 27 //因此，需要统计当前父节点每个子树编号出现的次数 28 map<int, int> count; 29 for (auto &child : children) { 30 count[child]++; 31 } 32 //oddcnt:奇数子树个数， badcnt:奇数且非对称子树个数 33 int oddcnt = 0, badcnt = 0; 34 for (auto &[child, cnt] : count) { 35 if (cnt & 1) { 36 oddcnt++, badcnt += !is_symmetrical[child]; 37 } 38 } 39 //更新结果到map里面 40 is_symmetrical[curr_size] = oddcnt < 2 && !badcnt; 41 get_index[children] = curr_size++; 42 } 43 return get_index[children]; 44 }; 45 46 int n; 47 cin >> n; 48 vector<vector<int>> list_node(n); 49 for (int i = 0; i < n - 1; i++) { 50 int u, v; 51 cin >> u >> v; 52 --u, --v; 53 list_node[u].emplace_back(v); 54 list_node[v].emplace_back(u); 55 } 56 cout << (is_symmetrical[dfs(dfs, 0, 0, list_node)] ? "YES" : "NO") << endl; 57 } 58 59 int main() { 60 int t = 1; 61 cin >> t; 62 while (t--) { 63 solve(); 64 } 65 return 0; 66 }