You are given a tree that is rooted at \(1\) and contains \(N\) nodes. Each node \(u\) has a value assigned to it that is denoted as \(Val_u\). A subset of nodes is selected in a random manner. Any node can be selected with equal probability.
The value of the subset is defined as follows:
Let the lowest common ancestor of these nodes be \(L\). If \(Val_L\) is greater than \(Val_u\) for all \(u\) belonging to this subset, then the score of this subset is \(u\). Otherwise, the score is \(1\). For an empty subset, the score is \(0\).
You must determine the expected score of the subset. The answer can be represented as \(\frac {P} {Q}\).
Print the answer as \(P \cdot Q^{-1}\) modulo \(10^{9}+7\).
Input format
- First line: A single integer \(N\) denoting the total number of nodes in the tree
- Next \(N-1\) lines: Two space-separated integers \(u\) and \(v\) denoting an edge between \(u\) and \(v\)
- Next line: \(N\) space-separated integers where the \(i^{th}\) integer denotes \(Val_i\)
Output format
Print the required value modulo \(10^{9}+7\) .
Constraints
Consider all the subsets:
{} - > Score = 0 for empty subset
{1} -> Lca = 1, Score = 1 , because value of node 1 is not less than that of lca, Score of subset is 1.
{2} -> Lca = 2, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{3} -> Lca = 3, Score = 1, because value of node 3 is not less than that of lca, Score of subset is 1.
{4} -> Lca = 4, Score = 1, because value of node 4 is not less than that of lca, Score of subset is 1.
{1,2} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{1,3} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{1,4} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{2,3} -> Lca = 2, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{2,4} -> Lca = 1, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{3,4} -> Lca = 1, Score = 1, because value of both nodes is less than that of lca, Score of subset is equal to that of lca which is 1 in this case.
{1,2,3} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{1,2,4} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{2,3,4} -> Lca = 1, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{1,2,3,4} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
Hence, the expected value is \(\frac {15} {16}\).
\(15 \cdot 16^{-1} \mod 10^{9}+7 = 437500004\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor