← 返回题目列表

Codeforces · 786/D

D. 说唱之神

中文机器翻译题面 查看原题

Rick 爱上了 Unity。但 Meeseeks 先生也热爱 Unity,所以 Rick 和 Meeseeks 先生是“情敌”。

Unity热爱说唱,因此决定他们必须参加说唱游戏(战斗)才能选出最好的。里克(Rick)太书呆子了,所以他会在歌词“Rap God”歌曲上运行他的原始算法来创作他的诗句。

他的算法有点复杂。他做了一棵树,有n个顶点,编号为1到n,每条边上都写着一个小写英文字母。他将str(a,b)表示为从a到b的最短路径的边上逐个写入字符而成的字符串(长度等于a到b的距离的字符串)。请注意,str(a, b) 与 str(b, a) 相反,并且 str(a, a) 为空。

为了写出最好的诗句,他需要回答一些问题,但他不是计算机科学家,无法回答这些问题,所以他请求你帮助他。每个查询都由两个顶点 x 和 y (x ≠ y) 来表征。此查询的答案是像 z 这样满足 z ≠ x、z ≠ y 且 str(x, y) 按字典顺序大于 str(x, z) 的顶点数量。

字符串 x = x1x2...x|x|按字典顺序大于字符串 y = y1y2...y|y|,如果 |x| > |y|且 x1 = y1,x2 = y2,...,x|y| = y|y|,或存在这样的数字 r (r < |x|, r < |y|),即 x1 = y1,x2 = y2,...,xr = yr 且 xr + 1 > yr + 1。字符的比较类似于 ASCII 代码(或字母顺序)。

帮助 Rick 得到那个女孩(或者 Unity 的任何性别)。

输入

输入的第一行包含两个整数 n 和 q (2 ≤ n ≤ 20000, 1 ≤ q ≤ 20000) — 分别是树中的顶点数和查询数。

接下来的 n - 1 行包含边缘。每行包含两个整数 v 和 u(边的端点),后跟一个英文小写字母 c (1 ≤ v, u ≤ n, v ≠ u)。

接下来的 q 行包含查询。每行包含两个整数 x 和 y (1 ≤ x, y ≤ n, x ≠ y)。

输出

在一行中打印每个查询的答案。

示例

输入 #1

4 3
4 1 t
3 2 p
1 2 s
3 2
1 3
2 1

输出 #1

0
1
1

输入 #2

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

输出 #2

6
1
3
1

注意

这是第一个示例测试用例的树:

这是第二个示例测试用例的树:

在此测试中:

- str(8, 1) = 便便
- str(8, 2) = 坡
- str(8, 3) = po
- str(8, 4) = 弹出
- str(8, 5) = popd
- str(8, 6) = popp
- str(8, 7) = p

因此,对于第一个查询, $$z \in \{1, 2, 3, 4, 5, 7\}$$ 是答案,对于第三个查询 $$z \in \{2, 3, 7\}$$ 是答案。