题目链接：http://csustacm.com:4803/problem/1006
题目：
思路：正如题目一样，本题是一个hash，比赛的时候用的字典树，但是不知道为什么一直RE（听学长说要动态开点，但是没学字典树，瞎套的板子，可能真的是我姿势不对吧~），赛后学了一边hash（字符串题只会上星期学的kmp）后把这题补了一下。这题就最后比较时需要将每个节点的从1到该节点路径上所有的字母组成一个新的字符串，然后与题目给的n个字符串进行匹配（匹配定义题目中有说），问是否所有的字符串都至少与给的n个字符串中的一个匹配，因此我们需要借助dfs来处理新的串，我们用一个vis来标记原来那n个字符串的字串的hash值，在跑dfs时顺便判定，降低复杂度。
代码实现如下：
1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <stack> 5 #include <cmath> 6 #include <bitset> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 #include <unordered_map> 15 using namespace std; 16 17 typedef long long ll; 18 typedef pair<ll, ll> pll; 19 typedef pair<ll, int> pli; 20 typedef pair<int, ll> pil;; 21 typedef pair<int, int> pii; 22 typedef unsigned long long ull; 23 24 #define lson i<<1 25 #define rson i<<1|1 26 #define bug printf("********* "); 27 #define FIN freopen("D://code//in.txt", "r", stdin); 28 #define debug(x) cout<<"["<<x<<"]" <<endl; 29 #define IO ios::sync_with_stdio(false),cin.tie(0); 30 31 const double eps = 1e-8; 32 const int mod = 10007; 33 const int maxn = 2e5 + 7; 34 const double pi = acos(-1); 35 const int inf = 0x3f3f3f3f; 36 const ll INF = 0x3f3f3f3f3f3f3f; 37 const ull p = 2333; 38 39 unordered_map<ull, int> vis; 40 int n, m, u, v, k, x; 41 int w[maxn]; 42 ull hs1, hs2[maxn]; 43 int tot; 44 int head[maxn]; 45 46 struct edge { 47 int v, next; 48 }ed[maxn<<1]; 49 50 void addedge(int u, int v) { 51 ed[tot].v = v; 52 ed[tot].next = head[u]; 53 head[u] = tot++; 54 ed[tot].v = u; 55 ed[tot].next = head[v]; 56 head[v] = tot++; 57 } 58 59 bool dfs(int u, int fa) { 60 for(int i = head[u]; ~i; i = ed[i].next) { 61 int v = ed[i].v; 62 if(v == fa) continue; 63 hs2[v] = hs2[u] * p + w[v]; 64 if(!vis[hs2[v]]) return false; 65 if(!dfs(v, u)) return false; 66 } 67 return true; 68 } 69 70 int main() { 71 //FIN; 72 scanf("%d%d", &n, &m); 73 memset(head, -1, sizeof(head)); 74 for(int i = 1; i <= n; i++) { 75 scanf("%d", &k); 76 hs1 = 0; 77 for(int j = 1; j <= k; j++) { 78 scanf("%d", &x); 79 hs1 = hs1 * p + x; 80 vis[hs1] = 1; 81 } 82 } 83 for(int i = 1; i <= m; i++) { 84 scanf("%d", &w[i]); 85 } 86 for(int i = 1; i < m; i++) { 87 scanf("%d%d", &u, &v); 88 addedge(u, v); 89 } 90 if(!vis[w[1]]) { 91 puts("NO"); 92 } else { 93 hs2[1] = w[1]; 94 if(dfs(1, 0)) puts("YES"); 95 else puts("NO"); 96 } 97 return 0; 98 }
补字典树写法：
1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <stack> 5 #include <cmath> 6 #include <bitset> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 #include <unordered_map> 15 using namespace std; 16 17 typedef long long ll; 18 typedef pair<ll, ll> pll; 19 typedef pair<ll, int> pli; 20 typedef pair<int, ll> pil;; 21 typedef pair<int, int> pii; 22 typedef unsigned long long ull; 23 24 #define lson i<<1 25 #define rson i<<1|1 26 #define bug printf("********* "); 27 #define FIN freopen("D://code//in.txt", "r", stdin); 28 #define debug(x) cout<<"["<<x<<"]" <<endl; 29 #define IO ios::sync_with_stdio(false),cin.tie(0); 30 31 const double eps = 1e-8; 32 const int mod = 10007; 33 const int maxn = 2e5 + 7; 34 const double pi = acos(-1); 35 const int inf = 0x3f3f3f3f; 36 const ll INF = 0x3f3f3f3f3f3f3f; 37 38 int len, root, k, m, n, x, y; 39 int w[maxn]; 40 vector<int> v, G[maxn]; 41 42 struct Trie { 43 int cnt; 44 map<int, int > nxt; 45 46 void init() { 47 cnt = 0; 48 nxt.clear(); 49 } 50 }T[maxn]; 51 52 void insert(int s) { 53 int now = root; 54 for(auto x : v[s]) { 55 if(T[now].nxt[x] == 0) { 56 T[len].init(); 57 T[now].nxt[x] = len++; 58 } 59 now = T[now].nxt[x]; 60 T[now].cnt++; 61 } 62 } 63 64 bool dfs(int u, int p, int now) { 65 int res = 1; 66 for(auto v : G[u]) { 67 if(v == p) continue; 68 if(T[now].nxt[w[v]] == 0) return 0; 69 res &= dfs(v, u, T[now].nxt[w[v]]); 70 } 71 return res; 72 } 73 74 int main() { 75 FIN; 76 scanf("%d%d", &n, &m); 77 len = 1, root = 0; 78 T[0].init(); 79 for(int i = 1; i <= n; i++) { 80 scanf("%d", &k); 81 for(int j = 1; j <= k; j++) { 82 scanf("%d", &x); 83 v[i].push_back(x); 84 } 85 insert(i); 86 } 87 for(int i = 1; i <= m; i++) { 88 scanf("%d", &w[i]); 89 } 90 for(int i = 1; i < m; i++) { 91 scanf("%d%d", &x, &y); 92 G[x].push_back(y); 93 G[y].push_back(x); 94 } 95 if(T[0].nxt[w[1]] == 0) puts("NO"); 96 else { 97 if(dfs(1, 0, T[0].nxt[w[1]])) puts("YES"); 98 else puts("NO"); 99 } 100 return 0; 101 }