J - MODクエリ

Contest Duration: 2015-10-24(Sat) 04:20 - 2015-10-24(Sat) 09:20 (local time) (300 minutes)

J - MODクエリ Editorial

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

頂点数 $n$ の木があり，頂点 $i (i = 1, ..., n)$ には正の整数 $a_i$ が書かれている． $q$ 個の質問に答えよ.

各質問は3つの整数からなり， $j$ 番目の質問は $x_j, v_j, w_j$ で与えられる．
木の頂点 $v_j$ から $w_j$ への最短のパスの頂点に書かれている数 $a_i$ で， $x_j$ を順番に割った余りを出力せよ．言い換えると， $v_j$ から $w_j$ への最短パスが $p_1, ..., p_k$ (頂点数 $k$ , $p_1 = v_j, p_k = w_j$ ) であるとき， $((...((x_j % a_{p_1}) % a_{p_2}) ...) % a_{p_{k-1}} ) % a_{p_k}$ を出力せよ．

ただし $x % y$ は $x$ を $y$ で割った余りを取る演算とする．

入力

1行目は数列の長さ $n$ と質問の数 $q$ が与えられる． 2行目には数列 $a$ を表す $n$ 個の正整数が空白区切りで与えられる．続く $n-1$ 行の各行には木の辺の端点 $b_i, c_i$ が空白区切りで与えられる．続く $q$ 行には各質問が与えられる．各質問は，3つの整数 $x_j, v_j, w_j$ が空白区切りで与えられる．

 $n$   $q$ 
 $a_1$  ...  $a_n$ 
 $b_1$   $c_1$ 
:
 $b_{n-1}$   $c_{n-1}$ 
 $x_1$   $v_1$   $w_1$ 
:
 $x_q$   $v_q$   $w_q$

$1 \leq n \leq 100000$
$1 \leq q \leq 100000$
$1 \leq a_i \leq 10^{9}$
$1 \leq b_i, c_i \leq n$
$0 \leq x_j \leq 10^{9}$
$1 \leq v_j, w_j \leq n$
入力値はすべて整数である
与えられるグラフは木である

出力

出力は $q$ 行からなる． $j$ 行目には $j$ 個目の質問に対する答えを1つの整数で出力せよ．

部分点

以下の制約を満たすデータセットに全て正解した場合は $30$ 点の部分点が与えられる．

全ての $i$ $(1 \leq i \leq n-1)$ について， $b_i = i, c_i = i+1$ ，つまりグラフはパスである
全ての $j$ $(1 \leq j \leq q)$ について， $v_j \leq w_j$ である

入力例1Copy

Copy

出力例1Copy

Copy

1
0

グラフはパスの構造をしている． 1個目の質問について， $15 % 8 = 7, 7 % 6 = 1, 1 % 4 = 1, 1 % 3 = 1, 1 % 2 = 1$ で，答は $1$ である． 2個目の質問について， $15 % 6 = 3, 3 % 4 = 3, 3 % 3 = 0, 0 % 2 = 0$ で，答は $0$ である．

入力例2Copy

Copy

8 5
18 29 52 64 4 59 89 15
1 2
1 3
1 4
2 5
3 6
3 7
4 8
99 6 7
102 5 8
15 2 6
84 7 8
19 1 1

出力例2Copy

Copy

Source Name

京都大学プログラミングコンテスト2015