시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
13 초 (추가 시간 없음) | 1024 MB | 39 | 15 | 12 | 38.710% |
One day Young Anna comes up with a whimsical idea of using a tree to create a number generator. The generator is created with a modulus m and an internal tree of n nodes numbered from 1 to n. Each tree node is assigned a single digit between 0 to 9. The generator provides a method Get(a, b) that can be used to produce an integer in [0, m). The two arguments a and b specify two tree nodes. The generator walks the path from a to b in the tree, concatenates all the digits along the path (including the digits of node a and b), and obtains a decimal integer v as a result of such digit concatenation. Note that v can be quite large and may contain leading zeroes. The return value of Get(a, b) is v modulo m.
Given a tree and the value of m to be used by Anna’s number generator, calculate the return values of q queries Get(a, b).
The first line of input has three integers n (2 ≤ n ≤ 2 · 105), m (1 ≤ m ≤ 109), and q (1 ≤ q ≤ 2 · 105).
The next n − 1 lines describe the tree edges. Each line has two integers x, y (1 ≤ x, y ≤ n) listing an edge connecting node x and node y. It is guaranteed that those edges form a tree.
The next n lines each have a single digit between 0 to 9. The ith digit is assigned to node i.
The next q lines each have two integers a, b (1 ≤ a, b ≤ n) specifying a query Get(a, b).
For each Get(a, b) query output its return value on a single line.
5 100 4 1 2 1 3 1 4 5 3 1 2 3 0 4 1 5 5 1 4 2 3 3
34 31 12 3
ICPC > Regionals > North America > Mid-Atlantic Regional > 2021 Mid-Atlantic USA Regional Contest K번
ICPC > Regionals > North America > North Central North America Regional > 2021 North Central NA Regional Contest B번