Rap God
Contest: Codeforces Round 406 (Div. 1)
Difficulty rating: 3400
Tags: data structures, dfs and similar, hashing, strings, trees

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.

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  =  x1x2...x|x| is lexicographically larger than string y  =  y1y2...y|y|, if either |x|  >  |y| and x1  =  y1,  x2  =  y2,  ...,  x|y|  =  y|y|, or exists such number r (r  <  |x|,  r  <  |y|), that x1  =  y1,  x2  =  y2,  ...,  xr  =  yr and xr  +  1  >  yr  +  1. Characters are compared like their ASCII codes (or alphabetic order).

Help Rick get the girl (or whatever gender Unity has).

Input format:
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 format:
Print the answer for each query in one line.

Constraints:
Time limit: 7.0 s
Memory limit: 256.0 MB

Note:
Here's the tree of first sample testcase:

Here's the tree of second sample testcase:

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, $$z \in \{1, 2, 3, 4, 5, 7\}$$ and for the third query $$z \in \{2, 3, 7\}$$ is the answer.

Example input:
4 3
4 1 t
3 2 p
1 2 s
3 2
1 3
2 1

Example output:
0
1
1

Example input:
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

Example output:
6
1
3
1

Editorial:
Use centroid-decomposition. In each decomposition:
Assume c is centroid of current subtree. Then for each vertex v in current subtree, we want to find some part of answer for each query with x = v. More precisely, for each query (x, y) that x is in the current subtree (in the decomposition), we want to find the number of vertices like z such that z is also in the subtree, if we remove the centroid from the tree z and x will be disconnected (centroid itself satisfies this condition) and str(x, z) < str(x, y).
str(x, z) = str(x, c) + str(c, z). So for each query first compare str(x, y) with str(x, c). Comparing two paths (str(x, y) and str(v, u)) can be done using hash (for each v and k, keep hash of str(v, 2i - th parent of v) and its reverse) and using binary search for finding LCP of two strings. Based on result of comparison:
• If str(x, y) < str(x, c), then there's no such z in current subtree.
• If str(x, y) > str(x, c) and str(x, c) is not a prefix of str(x, y), then all vertices like z that satisfy the first two conditions (from the three conditions above) are counted.
• Otherwise there's a vertex e on path from x to y such that str(x, w) = str(x, c). Because str(x, z) = str(x, c) + str(c, z) and str(x, y) = str(x, w) + str(w, y) = str(x, c) + str(w, y), then you have to count such z that satisfy the first two conditions and str(c, z) < str(w, y).
For the third case, you need to count vertices like z that str(c, z) < str(w, y). For this purpose, using a single DFS construct trie of all str(c, z) and then for each query find the position of str(w, y) in the trie (using hashes and binary search). More precisely, you need to find LCP of str(w, y) and strings in the trie to determine how many strings in the trie are less than str(w, y).
All of this can be done in $${\mathcal {O}}((n+q)\lg ^{2}(n))$$ And there's an additional log for centroid-decomposition, so:
Total time complexity: $${\mathcal {O}}((n+q)\lg ^{3}(n))$$