#P51637. 「LOJ」 字母树
「LOJ」 字母树
题目描述
给定一颗 个节点的无根树,每条边上附有一个小写英文字母。
于是一条路径对应一个字符串。
一共有 次询问,每次询问以节点 为起点的非空字符串中有多少字典序严格小于字符串 。
输入格式
第一行,两个个整数 。
接下来 行,每行两个整数,一个小写字母。 。 表示存在字母为 的树边 。保证 。
接下来 行,每行两个整数 。
输出格式
行,每行一个答案。
样例 1
4 3
4 1 t
3 2 p
1 2 s
3 2
1 3
2 1
0
1
1
第一个询问,以 为起点的字符串有p
,ps
,pst
。 生成p
。没有比p
字典序严格小的字符串。
第二个询问,以 为起点的字符串有s
,sp
,t
。 生成sp
。s
字典序比sp
小。
第二个询问,以 为起点的字符串有p
,s
,st
。 生成s
。p
字典序比s
小。
8 4
4 6 p
3 7 o
7 8 p
4 5 d
1 3 o
4 3 p
3 2 e
8 6
3 7
8 1
4 3
6
1
3
1
数据范围与提示