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;
}
|
