1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
| #include <bits/stdc++.h> using namespace std;
inline int read() { int x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); return x * f; }
int n, m, tot; int head[100005], pre[200005], to[200005], len[200005], sz; char s[200005][11], q[11];
inline int o(char ch) { return ch - 'a' + 1; }
inline void addedge(int u, int v) { pre[++sz] = head[u]; head[u] = sz; to[sz] = v; pre[++sz] = head[v]; head[v] = sz; to[sz] = u; }
namespace Trie{ struct trie{ int son[30], sz; } tr[5000005]; int rt[100005];
void insert(int d, int &ind, int lst, char *str) { ind = ++tot; tr[ind].sz = tr[lst].sz; if (str[d] < 'a' || str[d] > 'z') { tr[ind].sz++; return; } for (int i = 1; i <= 26; i++) { tr[ind].son[i] = tr[lst].son[i]; } insert(d+1, tr[ind].son[o(str[d])], tr[lst].son[o(str[d])], str); for (int i = 1; i <= 26; i++) { tr[ind].sz += tr[tr[ind].son[i]].sz - tr[tr[lst].son[i]].sz; } } int query(int d, int lind, int rind, char *str) { if (str[d] < 'a' || str[d] > 'z') { return max(0, tr[rind].sz - tr[lind].sz); } else return query(d+1, tr[lind].son[o(str[d])], tr[rind].son[o(str[d])], str); } }
using namespace Trie;
namespace Treechains{ int d[100005], dfn[100005], rnk[100005], tme, fa[100005], top[100005], siz[100005], son[100005], sonind[100005]; void dfs(int x, int fafa) { siz[x] = 1; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fafa) continue; d[y] = d[x] + 1; fa[y] = x; dfs(y, x); siz[x] += siz[y]; if (!son[x] || siz[y] > siz[son[x]]) son[x] = y, sonind[x] = i; } } void dfs2(int x, int tp) { dfn[x] = ++tme; rnk[tme] = dfn[x]; top[x] = tp; if (son[x]) { insert(1, rt[tme+1], rt[tme], s[sonind[x]]); dfs2(son[x], tp); } for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fa[x] || y == son[x]) continue; insert(1, rt[tme+1], rt[tme], s[i]); dfs2(y, y); } } inline int query_path(int x, int y) { int ret = 0; while (top[x] != top[y]) { if (d[top[x]] < d[top[y]]) swap(x, y); ret += query(1, rt[dfn[top[x]]-1], rt[dfn[x]], q); x = fa[top[x]]; } if (d[x] > d[y]) swap(x, y); ret += query(1, rt[dfn[x]], rt[dfn[y]], q); return ret; } }
using namespace Treechains;
int main() { n = read(); for (int i = 1; i < n; i++) { addedge(read(), read()); scanf("%s", s[sz-1]+1); len[sz-1] = len[sz] = strlen(s[sz-1]+1); for (int j = 1; j <= len[sz-1]; j++) s[sz][j] = s[sz-1][j]; } dfs(1, 0); dfs2(1, 1); m = read(); for (int i = 1; i <= m; i++) { int x = read(), y = read(); scanf("%s", q+1); query_path(x, y); printf("%d\n", query_path(x, y)); } return 0; }
|