English · Original
Chinese · Translation
Formal · Original
Rick is in love with Unity. But Mr. Meeseeks also love Unity, so Rick and Mr. Meeseeks are "love rivals".
Unity loves rap, so it decided that they have to compete in a rap game (battle) in order to choose the best. Rick is too nerds, so instead he's gonna make his verse with running his original algorithm on lyrics "Rap God" song.
<center></center>His algorithm is a little bit complicated. He's made a tree with _n_ vertices numbered from 1 to _n_ and there's a lowercase english letter written on each edge. He denotes _str_(_a_, _b_) to be the string made by writing characters on edges on the shortest path from _a_ to _b_ one by one (a string of length equal to distance of _a_ to _b_). Note that _str_(_a_, _b_) is reverse of _str_(_b_, _a_) and _str_(_a_, _a_) is empty.
In order to make the best verse he can, he needs to answer some queries, but he's not a computer scientist and is not able to answer those queries, so he asked you to help him. Each query is characterized by two vertices _x_ and _y_ (_x_ ≠ _y_). Answer to this query is the number of vertices like _z_ such that _z_ ≠ _x_, _z_ ≠ _y_ and _str_(_x_, _y_) is lexicographically larger than _str_(_x_, _z_).
String _x_ = _x_1_x_2..._x_|_x_| is lexicographically larger than string _y_ = _y_1_y_2..._y_|_y_|, if either |_x_| > |_y_| and _x_1 = _y_1, _x_2 = _y_2, ..., _x_|_y_| = _y_|_y_|, or exists such number _r_ (_r_ < |_x_|, _r_ < |_y_|), that _x_1 = _y_1, _x_2 = _y_2, ..., _x__r_ = _y__r_ and _x__r_ + 1 > _y__r_ + 1. Characters are compared like their ASCII codes (or alphabetic order).
Help Rick get the girl (or whatever gender Unity has).
## Input
The first line of input contain two integers _n_ and _q_ (2 ≤ _n_ ≤ 20000, 1 ≤ _q_ ≤ 20000) — number of vertices in tree and number of queries respectively.
The next _n_ - 1 lines contain the edges. Each line contains two integers _v_ and _u_ (endpoints of the edge) followed by an English lowercase letter _c_ (1 ≤ _v_, _u_ ≤ _n_, _v_ ≠ _u_).
The next _q_ line contain the queries. Each line contains two integers _x_ and _y_ (1 ≤ _x_, _y_ ≤ _n_, _x_ ≠ _y_).
## Output
Print the answer for each query in one line.
[samples]
## Note
Here's the tree of first sample testcase:
<center></center>Here's the tree of second sample testcase:
<center></center>In this test:
* _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_
So, for the first query, and for the third query is the answer.
Rick 爱上了 Unity。但 Mr. Meeseeks 也爱 Unity，因此 Rick 和 Mr. Meeseeks 成为了“情敌”。
Unity 喜欢说唱，于是决定让他们通过一场说唱对决（battle）来决出胜者。Rick 太宅了，所以他打算用自己设计的算法处理歌曲《Rap God》的歌词来创作他的 verse。
他的算法有点复杂。他构建了一棵包含 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]，每条边上写有一个小写英文字母。他记 #cf_span[str(a, b)] 为从 #cf_span[a] 到 #cf_span[b] 的最短路径上，按顺序写出各边上的字符所构成的字符串（字符串长度等于 #cf_span[a] 到 #cf_span[b] 的距离）。注意，#cf_span[str(a, b)] 是 #cf_span[str(b, a)] 的逆序，且 #cf_span[str(a, a)] 为空字符串。
为了创作出最好的 verse，他需要回答一些查询，但他不是计算机科学家，无法回答这些问题，因此他请你帮忙。每个查询由两个顶点 #cf_span[x] 和 #cf_span[y]（#cf_span[x ≠ y]）组成。该查询的答案是满足 #cf_span[z ≠ x, z ≠ y] 且 #cf_span[str(x, y)] 在字典序上大于 #cf_span[str(x, z)] 的顶点 #cf_span[z] 的数量。
字符串 #cf_span[x = x1x2...x|x|] 在字典序上大于字符串 #cf_span[y = y1y2...y|y|]，当且仅当：要么 #cf_span[|x| > |y|] 且 #cf_span[x1 = y1, x2 = y2, ..., x|y| = y|y|]，要么存在某个数 #cf_span[r (r < |x|, r < |y|)]，使得 #cf_span[x1 = y1, x2 = y2, ..., xr = yr] 且 #cf_span[xr + 1 > yr + 1]。字符按其 ASCII 码（或字母顺序）进行比较。
帮助 Rick赢得女孩（或 Unity 的任何性别）吧。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 20000]，#cf_span[1 ≤ q ≤ 20000]）——树的顶点数和查询数。
接下来的 #cf_span[n - 1] 行描述边。每行包含两个整数 #cf_span[v] 和 #cf_span[u]（边的端点），后跟一个小写英文字母 #cf_span[c]（#cf_span[1 ≤ v, u ≤ n, v ≠ u]）。
接下来的 #cf_span[q] 行包含查询。每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n, x ≠ y]）。
对每个查询，在一行中输出答案。
第一个样例测试用例的树如下：
第二个样例测试用例的树如下：
在本测试中：
因此，对于第一个查询，答案是 ；对于第三个查询，答案是 。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 20000]，#cf_span[1 ≤ q ≤ 20000]）——树的顶点数和查询数。接下来的 #cf_span[n - 1] 行描述边。每行包含两个整数 #cf_span[v] 和 #cf_span[u]（边的端点），后跟一个小写英文字母 #cf_span[c]（#cf_span[1 ≤ v, u ≤ n, v ≠ u]）。接下来的 #cf_span[q] 行包含查询。每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n, x ≠ y]）。
## Output
对每个查询，在一行中输出答案。
[samples]
## Note
第一个样例测试用例的树如下： 第二个样例测试用例的树如下： 在本测试中： #cf_span[str(8, 1)] = _poo_ #cf_span[str(8, 2)] = _poe_ #cf_span[str(8, 3)] = _po_ #cf_span[str(8, 4)] = _pop_ #cf_span[str(8, 5)] = _popd_ #cf_span[str(8, 6)] = _popp_ #cf_span[str(8, 7)] = _p_ 因此，对于第一个查询，答案是 ；对于第三个查询，答案是 。
**Definitions**
Let $ T = (V, E) $ be a tree with $ n $ vertices $ V = \{1, 2, \dots, n\} $, and each edge $ (u, v) \in E $ is labeled with a lowercase English letter.
For any two vertices $ a, b \in V $, let $ \text{str}(a, b) $ denote the string formed by concatenating the labels of edges along the unique simple path from $ a $ to $ b $ (empty if $ a = b $).
Note: $ \text{str}(a, b) = \text{reverse}(\text{str}(b, a)) $.
**Constraints**
1. $ 2 \le n \le 20000 $
2. $ 1 \le q \le 20000 $
3. Each edge label is a lowercase English letter.
4. For each query: $ x \ne y $, $ x, y \in V $
**Objective**
For each query $ (x, y) $, compute:
$$
\left| \left\{ z \in V \mid z \ne x,\ z \ne y,\ \text{str}(x, y) \succ \text{str}(x, z) \right\} \right|
$$
where $ \succ $ denotes lexicographic order:
- $ s \succ t $ if either:
(i) $ |s| > |t| $ and $ s[1..|t|] = t $, or
(ii) $ \exists r < \min(|s|, |t|) $ such that $ s[1..r] = t[1..r] $ and $ s[r+1] > t[r+1] $ (by ASCII order).
API Response (JSON)
{
"problem": {
"name": "D. Rap God",
"description": {
"content": "Rick is in love with Unity. But Mr. Meeseeks also love Unity, so Rick and Mr. Meeseeks are \"love rivals\". Unity loves rap, so it decided that they have to compete in a rap game (battle) in order to c",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 7000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF786D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Rick is in love with Unity. But Mr. Meeseeks also love Unity, so Rick and Mr. Meeseeks are \"love rivals\".\n\nUnity loves rap, so it decided that they have to compete in a rap game (battle) in order to c...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Rick 爱上了 Unity。但 Mr. Meeseeks 也爱 Unity，因此 Rick 和 Mr. Meeseeks 成为了“情敌”。\n\nUnity 喜欢说唱，于是决定让他们通过一场说唱对决（battle）来决出胜者。Rick 太宅了，所以他打算用自己设计的算法处理歌曲《Rap God》的歌词来创作他的 verse。\n\n他的算法有点复杂。他构建了一棵包含 #cf_span[n] 个顶点的树，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T = (V, E) $ be a tree with $ n $ vertices $ V = \\{1, 2, \\dots, n\\} $, and each edge $ (u, v) \\in E $ is labeled with a lowercase English letter. \nFor any two vertices $ a, b ...",
"is_translate": false,
"language": "Formal"
}
]
}