#P18919. [2026多校联测]树的价值

[2026多校联测]树的价值

树的价值

题目描述

给定一棵 nn 个点的树,每条边上有一个小写字母。有 qq 个人想要购买它。对名字为字符串 SS 的人,树的价值是满足以下条件的有序点对 (u,v)(u,v) 的数量:从 uu 到 vv 的简单路径上,各边字符按顺序拼接后恰好等于 SS。

请对每个人的名字求出对应的价值。

输入格式

第一行两个整数 n,qn,q。

接下来 n−1n-1 行,每行两个整数 u,vu,v 和一个小写字母 cc,表示一条树边及其字符。

接下来 qq 行,第 ii 行一个字符串 SiS_i,表示第 ii 个人的名字。

输出格式

输出 qq 行,每行一个整数,表示第 ii 个人心目中树的价值。

样例 1

输入

5 8
1 2 a
2 3 b
2 4 a
4 5 c
a
b
c
ab
ba
aa
ac
abc

输出

4
2
2
2
2
2
1
0

样例 2

输入

7 10
1 2 a
1 3 b
2 4 c
2 5 a
3 6 a
6 7 b
a
b
c
ab
ba
ac
ca
bb
aba
cab

输出

6
4
2
3
3
2
2
0
2
1

样例 3

输入

15 18
1 2 a
1 3 b
2 4 a
2 5 c
3 6 a
3 7 b
4 8 c
4 9 a
5 10 b
5 11 a
6 12 c
6 13 b
7 14 a
14 15 c
a
b
c
ab
ba
ac
ca
bc
cb
aa
bb
abc
bac
aca
aba
cab
abb
cba

输出

12
8
8
6
6
7
7
2
2
4
2
0
4
4
4
4
2
0

数据范围

对于所有数据,1≤n,q≤2×1051\le n,q\le2\times10^5。令 m=∑i=1q∣Si∣m=\sum_{i=1}^q|S_i|,有 m≤4×105m\le4\times10^5。输入中的所有字符串均为英文小写字符串。

子任务 n≤n\le q≤q\le m≤m\le 特殊性质 分值
1 50005000 无 15
2 10510^5 2020 4×1054\times10^5 20
3 500500
4 10510^5 10510^5 树为一条链 15
5 2×1052\times10^5 无 10
6 2×1052\times10^5 4×1054\times10^5 20

更多样例见附加文件 samples.zip。