시간 제한메모리 제한제출정답맞힌 사람정답 비율
60 초 1024 MB75466.667%

문제

There are $N$ events, numbered $1$ through $N$. The probability of occurrence of each event depends upon the occurrence of exactly one other event called the parent event, except event $1$, which is an independent event. In other words, for each event from $2$ to $N$, $3$ values are given: $P_i$ denoting the parent event of event $i$, $A_i$ denoting the probability of occurrence of event $i$ if its parent event occurs, and $B_i$ denoting the probability of occurrence of event $i$ if its parent event does not occur. For event $1$, its probability of occurrence $K$ is given. There are $Q$ queries that we want to answer. Each query consists of $2$ distinct events, $u_j$ and $v_j$, and you need to find the probability that both events $u_j$ and $v_j$ have occurred.

입력

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains two integers $N$ and $Q$ denoting the number of events and number of queries, respectively. $N$ lines follow. The $i$-th line describes event $i$. The first line contains a single integer $K$ denoting the probability of occurrence of event $1$ multiplied by $10^6$. Each of the next $N-1$ lines consists of three integers $P_i$, $A_i$ and $B_i$ denoting the parent event of event $i$, the probability of occurrence of event ii if its parent event occurs multiplied by $10^6$, and the probability of occurrence of event $i$ if its parent event does not occur multiplied by $10^6$, respectively. Then, $Q$ lines follow, describing the queries. Each of these lines contains two distinct integers $u_j$ and $v_j$. For each query, find the probability that both events $u_j$ and $v_j$ occurred.

출력

For each test case, output one line containing Case #x: R1 R2 R3 … RQ, where $x$ is the test case number (starting from 1) and $R_j$ is the sought probability computed for $j$-th query modulo $10^9+7$, which is defined precisely as follows. Represent the answer of $j$-th query as an irreducible fraction $\frac{p}{q}$. The number $R_j$ then must satisfy the modular equation $R_j × q ≡ p(\text{mod }(10^9+7))$, and be between $0$ and $10^9+6$, inclusive. It can be shown that under the constraints of this problem such a number $R_j$ always exists and is uniquely determined.

제한

  • $1≤T≤100$.
  • $1≤P_i
  • $1≤u_j,v_j≤N$ and $u_j≠v_j$, for all $j$.
  • $0≤A_i≤10^6$, for each $i$ from $2$ to $N$.
  • $0≤B_i≤10^6$, for each $i$ from $2$ to $N$.
  • $0≤K≤10^6$.

Test Set 1 (18점)

  • $2≤N≤1000$.
  • $1≤Q≤1000$.

Test Set 2 (22점)

For at most 5 cases:

  • $2≤N≤2×10^5$.
  • $1≤Q≤2×10^5$.

For the remaining cases:

  • $2≤N≤1000$.
  • $1≤Q≤1000$.

예제 입력 1

2
5 2
200000
1 400000 300000
2 500000 200000
1 800000 100000
4 200000 400000
1 5
3 5
4 2
300000
1 100000 100000
2 300000 400000
3 500000 600000
1 2
2 4

예제 출력 1

Case #1: 136000001 556640004
Case #2: 710000005 849000006

For Sample Case #1, for the first query, the probability that both events $1$ and $5$ occurred is given by (the probability that event $1$ occurred) $×$ (probability that event $5$ occurs given event $1$ occurred). Event $1$ would occur with probability $0.2$. Given that event $1$ occurred, the probability that event $4$ occurs is $0.8$. Therefore, the probability of occurrence of event $5$ given that event $1$ occurred is $0.2×0.8+0.4×0.2=0.24$ (probability of event $5$ occurring given than event $4$ occurred $+$ probability of event $5$ occurring given that event $4$ did not occur). The probability that both events $1$ and $5$ occurred is $0.2×0.24=0.048$. The answer $0.048$ can be converted into fraction of $\frac{6}{125}$, and one can confirm that the $136000001$ satisfies the conditions mentioned in the output section as $136000001 × 125 ≡ 6(\text{mod }(10^9+7))$ and is uniquely determined. For the second query, the probability that both events $5$ and $3$ occurred is $0.10352$.

For Sample Case #2, for the first query, the probability that both events $1$ and $2$ occurred is given by (the probability that event $1$ occurred) $×$ (probability that event $2$ occurs given event $1$ occurred). As $1$ is the parent event of event $2$, the probability of event $2$ occurring given event $1$ occurred is $A_2$ which is $0.1$. Hence, the probability that both events $1$ and $2$ occurred is $0.3×0.1$. Hence, the output will be $3 × 10^{-2}\text{ mod }(10^9+7)=710000005$. For the second query, the probability of occurrence of both events $2$ and $4$ is $0.057$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.