CF786D Rap God

Rick 爱上了 Unity。但 Mr. Meeseeks 也爱 Unity，因此 Rick 和 Mr. Meeseeks 成为“情敌”。 Unity 喜欢 rap，于是它决定他们必须通过一场 rap 对决来决出谁更优秀。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 \neq y$）。请你计算，有多少个结点 $z$ 满足 $z \neq x,z \neq y$，且 $str(x,y)$ 字典序大于 $str(x,z)$。 字符串 $x=x_1x_2...x_{|x|}$ 字典序大于字符串 $y=y_1y_2...y_{|y|}$，当且仅当 $|x|>|y|$ 且 $x_1=y_1,x_2=y_2,...,x_{|y|}=y_{|y|}$，或存在某个 $r\ (r

第一行输入两个整数 $n$ 和 $q$（$2 \leq n \leq 20000$，$1 \leq q \leq 20000$）——树的结点数和询问数量。 接下来 $n-1$ 行描述树的边。每行包含两个整数 $v$ 和 $u$（边的两个端点），以及一个小写字母 $c$（$1 \leq v,u \leq n, v \neq u$）。 接下来 $q$ 行，每行两个整数 $x$ 和 $y$（$1 \leq x,y \leq n, x \neq y$），表示一个询问。

对于每个询问，输出一行答案。

下面是第一个样例的树结构：  下面是第二个样例的树结构：  在这个测试中： - $str(8,1) = $ poo - $str(8,2) = $ poe - $str(8,3) = $ po - $str(8,4) = $ pop - $str(8,5) = $ popd - $str(8,6) = $ popp - $str(8,7) = $ p 因此，对于第一个询问，，对于第三个询问  是答案。 由 ChatGPT 5 翻译