409671: GYM103677 H Alexander the Grape

Long ago, in Ancient Greek times, there lived a great conqueror, Alexander the Grape. He was known for his ability to expand his empire, all while planting miles and miles of grape vines along the way to mark where he had already been so as not to conquer the same civilization twice.

As Alexander's second-in-command, you are tasked with keeping up a ledger of the grape vines which have been laid across the lands. For each vine, you keep track of which two civilizations the vine connects (we will call these civilization $$$A$$$ and civilization $$$B$$$). You also keep track of which type of grapes will eventually grow on the vines since each vine can grow into either red or green grapes. A red grape vine indicates that Alexander's army can choose to travel from civilization $$$A$$$ to civilization $$$B$$$, but not from civilization $$$B$$$ to civilization $$$A$$$. Conversely, a green grape vine indicates that Alexander's army can choose to travel from civilization $$$B$$$ to civilization $$$A$$$, but not from civilization $$$A$$$ to civilization $$$B$$$.

Originally, Alexander the Grape was entirely certain that this, albeit complex, system of grape vines would be the key to directing his army from civilization to civilization so as to conquer as many of them as possible. Unfortunately, Alexander was quite hasty while planting the grape vines, and he does not remember with certitude which type of grapes were planted at the location of each vine.

Instead, Alexander only tells you with what probability the grapes will grow to be red. If Alexander dictates to you that a particular vine has probability $$$p$$$ to grow to be a red grape vine, then it also has a $$$1 - p$$$ probability to grow to be a green grape vine. It is assumed that $$$0 \leq p \leq 1$$$, of course.

Now, it is finally spring time and this means two things: firstly, it means that all grape vines now bear grapes and have grown according to probabilities dictated by Alexander the Grape, and secondly, it means that it is time for Alexander's army to conquer!

The lands are denoted by a collection of $$$N$$$ civilizations and $$$N - 1$$$ grape vines laid by Alexander and his army. It is guaranteed that, without the consideration of grape types, there is a unique path between every pair of civilizations. The remaining information available to you is the ledger of the grape vine information as dictated by Alexander. As its almost time to embark on another conquest, Alexander needs to consider his options on which civilization to begin his conquest from. The success of a conquest (measured in the number of unique civilizations visited) is quite important to Alexander, and as such, he would like you to calculate the following quantity: given that he chooses a starting civilization uniformly at random, and that the grape vines will grow with their predetermined probabilities, what is the expected number of reachable civilizations?

It's imperative that Alexander learns the result of this calculation as soon as possible in order to prepare the correct amount of weaponry, water, and food (in the form of raisins, of course) to pack for his army. Can you aid him in his calculations?

The input will begin with a line containing $$$N\ (1 \leq N \leq 10^5)$$$, the total number of civilizations.

The next $$$N - 1$$$ lines will each consist of four space-separated integers. Each of these lines will describe a grape vine.

The first two integers, $$$A, B\ (1 \leq A, B \leq N, A \neq B)$$$ denote the two civilizations that the respective grape vine connects, as defined in the description.

The next two integers, $$$P, Q\ (1 \leq P \leq Q < 10^9 + 7)$$$ denote the probability that the respective grape vine will bear red grapes. Note that $$$P$$$ and $$$Q$$$ are guaranteed to be relatively prime, that is, $$$P$$$ and $$$Q$$$ share no common divisors greater than 1, and that they collectively represent the probability $$$\frac{P}{Q}$$$.

The output should consist of a single integer denoting the expected value of the number of reachable civilizations given the grape vine probabilities and a uniformly randomly distributed choice of starting civilization.

Note that this expected value can be represented as a fraction $$$\frac{X}{Y}$$$ where $$$X$$$ and $$$Y$$$ are relatively prime, that is $$$X$$$ and $$$Y$$$ share no common divisors greater than 1. Therefore, the expected output will consist of $$$XY^{-1}\ (\text{mod } 10^9 + 7)$$$ where $$$Y^{-1}$$$ denotes the modular multiplicative inverse of $$$Y$$$ modulo $$$10^9 + 7$$$. The modular multiplicative inverse of an integer $$$Y$$$ modulo $$$10^9 + 7$$$ an integer $$$Z$$$ which satisfies the property $$$YZ \equiv 1\ (\text{mod } 10^9 + 7)$$$.

3
1 3 1 2
1 2 2 3

833333341

In the sample case, we are given a graph that has an edge between civilizations 1 and 2 and another edge between civilizations 1 and 3.

There is a $$$\frac{1}{2}$$$ chance that the edge between civilizations 1 and 3 will be directed from civilization 1 to civilization 3 and a $$$\frac{1}{2}$$$ chance that the edge will be directed in the opposite direction.

There is a $$$\frac{2}{3}$$$ chance that the edge between civilizations 1 and 2 will be directed from civilization 1 to civilization 2 and a $$$\frac{1}{3}$$$ chance that the edge will be directed in the opposite direction.

If Alexander begins at civilization 1, he may visit civilization 1 with certitude, civilization 2 with a probability of $$$\frac{1}{2}$$$, and civilization 3 with a probability of $$$\frac{2}{3}$$$. Thus the expected number of visited civilizations is $$$1 + \frac{1}{2} + \frac{2}{3} = \frac{13}{6}$$$.

If Alexander begins at civilization 2, he may visit civilization 2 with certitude, civilization 1 with a probability of $$$\frac{1}{3}$$$, and civilization 3 with a probability of $$$\frac{1}{3} \cdot \frac{1}{2}$$$. Thus the expected number of visited civilizations is $$$1 + \frac{1}{3} + \frac{1}{3} \cdot \frac{1}{2} = \frac{3}{2}$$$.

If Alexander begins at civilization 3, he may visit civilization 3 with certitude, civilization 1 with a probability of $$$\frac{1}{2}$$$, and civilization 2 with a probability of $$$\frac{1}{2} \cdot \frac{2}{3}$$$. Thus the expected number of visited civilizations is $$$1 + \frac{1}{2} + \frac{1}{2} \cdot \frac{2}{3} = \frac{11}{6}$$$.

Since Alexander's beginning civilization is uniformly random, the expected number of visited civilizations is $$$\frac{\frac{13}{6} + \frac{3}{2} + \frac{11}{6}}{3} = \frac{11}{6}$$$.

Note that $$$11 \cdot 6^{-1}\ (\text{mod } 10^9 + 7) = 833333341$$$.