import java.util.*; /* * Problem: Random Heap (NAIPC19) * Author: Alex Coleman * Complexity: O(n^3) * * First, assume the problem is that each node must be >= its children. * We can transform our solution to the <= version by making each node a random value in [-b,0] instead of [0,b] * * Consider the PDF of a single node independent of other nodes (conceptually PDF is the relative * 'odds' of taking on a value, s.t. the odds x is in [a,b] = integral of PDF from a to b). It * is defined as the piecewise function f(x)={x=0..b: 1/b}. For leaf nodes w.r.t. their subtree * (w.r.t. subtree meaning ensuring it is >= everything in its subtree), this is still their PDF. * For other nodes, their PDF w.r.t. subtree can be thought of as their independent PDF multiplied by each child's CDF (w.r.t their subtree). * This is because for our subtree's root node to take on a given value, first it must select the number, * then every child must select a smaller value. Given PDF(x) = PDF of a random variable taking on value x, * CDF(x) = integral PDF(x) = odds the variable takes on a value <= x. * * So we recursively compute the CDF for every node w.r.t. it's subtree by: * CDF(node) = integral from 0 to x of ({x=0..b: 1/b} * [product across children of CDF(child)])dx * * Given the CDF of the root w.r.t it's subtree, the answer is simply CDF(infinity) (i.e. the odds it takes on any value) * * Complexity analysis: * Our functions will be piecewise polynomials with at most n segments (the n max values for nodes are cutoffs). This adds a factor of n to our complexity. * Then, we can see that the degree of the CDF for a given node is equal to the subtree size (when we multiply with children we add their degrees, and * when we integrate we add one). Since we have to multiply (O(a*b)) and integrate (O(d)) in each node, a naive bounding would be * n^2 per node per piecewise function, so n^4 overall. However, our multiplication will only take an amortized O(n^2) per piecewise segment across * all nodes. To prove this, think of the polynomial multiplication as matching two nodes. It's complexity is |A|*|B| where A and B are the two subtrees being * multiplied. Think of this as pairing every element of A with an element of B. Thus the total complexity is equal to the total number of times nodes are paired. * Any two nodes are only paired once though (at their LCA). Thus the amortized complexity of the multiplication is n^2 per segment, giving * an overall complexity of O(n^3). */ public class RandomHeap_arc { static int mod = (int) 1e9 + 7, oo = (int)1e9+1; static long[] inv; static int[] bs; static ArrayList[] cs; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); inv = new long[n+1]; for(int i=1;i<=n;i++) inv[i] = inv(i); bs = new int[n]; cs = new ArrayList[n]; for (int i = 0; i < n; i++) cs[i] = new ArrayList<>(); int root = -1; for (int i = 0; i < n; i++) { bs[i] = in.nextInt(); int p = in.nextInt() - 1; if (p >= 0) cs[p].add(i); else root = i; } Piecewise res = solve(root); long ans = res.ps[res.m - 1].cs[0]; if(ans < 0) ans += mod; System.out.println(ans); } static Piecewise solve(int node) { Piecewise pdf = new Piecewise( new Polynomial[] { new Polynomial(0), new Polynomial(inv(bs[node])), new Polynomial(0) }, new int[] { -bs[node], 0, oo }); for (int c : cs[node]) pdf = pdf.multiply(solve(c)); return pdf.integrate(); } static long inv(long x) { return pow(x,mod-2); } static long pow(long x, long e) { long y = 1; while(e > 0) { if((e & 1) != 0) y = y*x%mod; x = x*x%mod; e >>= 1; } return y; } // f(x)=p[i](x) in [r[i-1], r[i]]; r[-1]=-oo static class Piecewise { Polynomial[] ps; int[] rs; int m; Piecewise(Polynomial[] ps, int[] rs) { this.ps = ps; this.rs = rs; m = ps.length; } Piecewise multiply(Piecewise p) { return multiply(this, p); } static Piecewise multiply(Piecewise p, Piecewise q) { Polynomial[] ps = new Polynomial[p.m + q.m]; int[] rs = new int[p.m + q.m]; int left = -oo, n = 0; for (int a = 0, b = 0; a < p.m && b < q.m; n++) { ps[n] = p.ps[a].multiply(q.ps[b]); rs[n] = Math.min(p.rs[a], q.rs[b]); left = rs[n]; while (a < p.m && p.rs[a] == left) a++; while (b < q.m && q.rs[b] == left) b++; } return new Piecewise(Arrays.copyOf(ps, n), Arrays.copyOf(rs, n)); } Piecewise integrate() { Polynomial[] nps = new Polynomial[m]; int[] nrs = new int[m]; long C = 0; int left = -oo; for (int i = 0; i < m; i++) { nps[i] = ps[i].integrate(); nrs[i] = rs[i]; nps[i].add(C - nps[i].eval(left)); C = nps[i].eval(nrs[i]); left = nrs[i]; } return new Piecewise(nps, nrs); } } static class Polynomial { int n; long[] cs; Polynomial(long[] cs) { this.cs = cs; n = cs.length; } Polynomial(long c0) { this(new long[] {c0}); } void add(long x) { cs[0] = (cs[0] + x) % mod; } Polynomial multiply(Polynomial p) { return multiply(this, p); } static Polynomial multiply(Polynomial p, Polynomial q) { long[] cc = new long[p.n + q.n - 1]; for (int i = 0; i < p.n; i++) for (int j = 0; j < q.n; j++) cc[i + j] = (cc[i + j] + p.cs[i] * q.cs[j]) % mod; return new Polynomial(cc); } Polynomial integrate() { long[] cc = new long[n + 1]; for (int i = 1; i <= n; i++) cc[i] = (cs[i - 1] * inv[i]) % mod; return new Polynomial(cc); } long eval(long x) { long xpow = 1; long y = 0; for (int i = 0; i < n; i++) { y = (y + xpow * cs[i]) % mod; xpow = xpow * x % mod; } return y; } } }