시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 1024 MB 24 17 12 70.588%

문제

$N$개의 정점으로 이루어진 트리 $T_{N}$를 다음과 같은 방법으로 생성한다.

  • $T_{1}$은 1번 정점만으로 이루어진 트리다.
  • 2 이상의 $i$에 대해 $T_{i}$는 $T_{i-1}$에 $i$번 정점을 $T_{i-1}$의 정점 중 하나와 간선으로 이어 추가한 트리다. $i$번 정점과 연결된 정점이 $j$번 정점이 될 확률은 $\frac{a_j}{a_1+ \cdots + a_{i-1}}$이다. $i$번 정점과 연결된 정점이 $j$번 정점이라면 그 간선의 길이는 $c_i + c_j$이다.

$Q$개의 쿼리가 주어진다. 각 쿼리로 $u$와 $v$가 주어질 때마다 $T_{N}$에서 $u$번 정점과 $v$번 정점의 거리의 기댓값을 구하여라.

입력

첫 번째 줄에 $N$과 $Q$가 주어진다. $(2 \leq N,Q \leq 300\,000)$

두 번째 줄에 $N-1$개의 정수 $a_1,a_2, \cdots, a_{N-1}$이 공백으로 구분되어 주어진다. $(1 \leq a_i \leq 2\,000)$

세 번째 줄에 $N$개의 정수 $c_1,c_2, \cdots, c_N$이 공백으로 구분되어 주어진다. $(1 \leq c_i \leq 2\,000)$

이후 $Q$개의 줄에 걸쳐 쿼리들이 주어진다. 각 줄에는 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$

출력

$i$번째 쿼리의 답을 $ans_i=\frac{p_i}{q_i}$라 하자. ($p_i$, $q_i$는 서로소인 음이 아닌 정수) $i$번째 줄에는 $p_i \equiv q_i x_i \pmod{10^9+7}$를 만족하는 $0$ 이상 $10^9+7$ 미만의 정수 $x_i$를 출력한다. 이 수는 유일하게 존재함을 증명할 수 있다.

예제 입력 1

5 7
1 1 1 1
1 2 4 8 16
1 3
2 5
4 3
1 5
3 3
4 5
1 2

예제 출력 1

7
666666697
15
666666697
0
333333366
3

예제 입력 2

5 4
17 19 23 29
2 3 5 7 11
1 2
3 4
5 2
3 5

예제 출력 2

5
927495315
106531441
450222593

출처

High School > 경기과학고등학교 > 나는코더다 2020 송년대회 A번