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

J - MODクエリ


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 256MB

問題文

頂点数 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 % yxy で割った余りを取る演算とする.


入力

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 である


入力例1

5 2
8 6 4 3 2
1 2
2 3
3 4
4 5
15 1 5
15 2 5

出力例1

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 である.

入力例2

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

出力例2

40
2
15
14
1

Source name

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

Submit提出する