#P18919. [2026多校联测]树的价值
[2026多校联测]树的价值
树的价值
题目描述
给定一棵 个点的树,每条边上有一个小写字母。有 个人想要购买它。对名字为字符串 的人,树的价值是满足以下条件的有序点对 的数量:从 到 的简单路径上,各边字符按顺序拼接后恰好等于 。
请对每个人的名字求出对应的价值。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 和一个小写字母 ,表示一条树边及其字符。
接下来 行,第 行一个字符串 ,表示第 个人的名字。
输出格式
输出 行,每行一个整数,表示第 个人心目中树的价值。
样例 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 | 无 | 15 | |||
| 2 | 20 | ||||
| 3 | |||||
| 4 | 树为一条链 | 15 | |||
| 5 | 无 | 10 | |||
| 6 | 20 | ||||
更多样例见附加文件 samples.zip。