P6088 [JSOI2015] String Tree

Mengmeng bought a seed of a string tree. If she plants it in spring, by summer it will grow into a huge string tree. The string tree is very special: its branches are densely covered with strings, and it looks very complicated.

A string tree is essentially still a tree, i.e., a connected undirected acyclic graph with $N$ nodes and $N-1$ edges, where nodes are numbered from $1$ to $N$. Different from an ordinary tree, each edge in the tree corresponds to a string. When Mengmeng and JYY are playing under the tree, Mengmeng decides to test JYY. Each time, Mengmeng writes down a string $S$ and two nodes $U, V$. JYY needs to immediately answer: on the shortest path between $U$ and $V$ (i.e., the path with the fewest edges; since it is a tree, this path is unique), how many edge strings have $S$ as a prefix. Although JYY is good at programming, he is not good at string processing. So he asks you to help solve Mengmeng's problem.

The first line contains an integer $N$, representing the number of nodes in the string tree. The next $N-1$ lines each contain two integers $U, V$, followed by a string $S$, meaning there is an edge directly connecting node $U$ and node $V$, and the string on this edge is $S$. The input guarantees that the given graph is a valid tree. The next line contains an integer $Q$, representing the number of questions from Mengmeng. The next $Q$ lines each contain two integers $U, V$, followed by a string $S$, meaning the question asks: on the shortest path between node $U$ and node $V$, how many edge strings have $S$ as a prefix.

Output $Q$ lines. Each line should contain the answer to the corresponding question.

For $100\%$ of the testdata, $1 \leq N, Q \leq 10^5$. The total length of all input strings does not exceed $10$, and all strings contain only lowercase letters `a~z`. Translated by ChatGPT 5