Heaps of Fun
Time limit2sMemory limit512 MB
Given a rooted tree where each node i draws a uniform random real in [0, b_i], compute the probability that every parent's value is less than both its children's values, modulo 1e9+7.
- Level
Hard8 of 10
- Topics
- Probability, Dynamic programming, Tree, Math
- Solved
- No attempts yet
Problem
Consider a rooted tree with n nodes, numbered 1 to n. Each node has a fixed integer b, and for each node a uniform random real number is chosen in the interval [0..b].
Find the probability that the chosen random numbers make the tree a Heap, meaning the random value in each node is less than the random values in its children.
This probability can always be written as a rational number P/Q with Q ≠ 0 (mod 10^9+7). Output the probability as P·Q^−1 mod 10^9+7, where Q^−1 is the integer that is the multiplicative inverse of Q modulo 10^9+7 (Q·Q^−1 ≡ 1 (mod 10^9+7)). (Note: P·Q^−1 mod 10^9+7 does not depend on whether P and Q are relatively prime, only on their ratio P/Q.)
Input
Each test case begins with a line containing a single integer n (1 ≤ n ≤ 300), the number of nodes in the tree.
Each of the next n lines contains a pair of space-separated integers b (1 ≤ b ≤ 10^9) and p (0 ≤ p ≤ n) describing a node of the tree, where b is the fixed integer value in the node and p is the node number of its parent. The nodes are listed in order: node 1 first, then node 2, and so on. Exactly one node has a parent p=0. This is the root of the tree.
Output
Output a single integer, the probability expressed as (P·Q^−1) mod (10^9+7).