There is nothing that Tobby, as a dog, enjoys more than bones. That’s why he has been studying the skeleton of certain species to figure out how much fun he could have with their bones. Tobby models a skeleton as a weighted tree whose edges represent the bones and their weights denote the lengths of the bones. Thus, the nodes are simply the joints connecting different bones. For Tobby it is quite hard to play with an entire skeleton, so he prefers to take a chain of connected bones instead, or, in other words, a simple path connecting two nodes in the skeleton tree. Moreover, since Tobby is a greedy dog, his happiness with a particular chain of bones doesn’t depend only on the chain’s size but on the length of the largest bone present in the chain as well, and here is where Tobby needs some help from you. It turns out that even for members of the same species there are variations on the length of the bones that make up the skeleton (the skeleton itself keeps fixed across members). Therefore, Tobby decided to model the bone lengths (i.e. edge weights) as discrete uniform random variables. This means that the weight wi associated with the i-th edge takes integer values in the closed interval [ai,bi]. Tobby has Q queries for you. Given a description of the tree and the weight random variables, for each query Tobby wants to know the expected value over the length of the largest bone present in a bones chain from joint xq to join yq. Formally, if w1, w2, ..., ws are the random variables denoting the edge’s weights in the simple path from xq to yq, you are required to compute E[max(w1, w2, . . . , ws)]. Input The input contains multiple test cases. For each test case the first line contains an integer N (2 ≤ N ≤ 50000) denoting the number of nodes in the tree of bones. Each of the following N − 1 lines describes anedgewith4integers: xi,yi,ai,bi (xi ̸=yi,1≤xi,yi ≤N,0≤ai ≤bi ≤100)wherexi andyi represent two different nodes connected by the edge whose weight can take discrete values uniformly in [ai,bi] (It’s guaranteed that the given graph is a tree). Next, the number of queries Q is given and then, Q (1 ≤ Q ≤ 100000) more lines follow describing each query with two different nodes xq and yq (xq ̸= yq, 1 ≤ xq,yq ≤ N) which represent both ends in a bones chain of interest for Tobby. The input specification ends with EOF. Output For each test case there must be Q output lines answering the Q test case queries. For each of these queries print in a single line the expected value of the largest edge weight in the simple path connecting the queried nodes. Your answer will be considered correct if the absolute difference with the jury’s answer is less than 10−5. Sample Input 6 1 2 0 50 2 3 30 40 2 4 10 80 4 5 50 90 4 6 95 100 3 16
2/2 35 24 2 1 2 0 100 1 21 Sample Output 97.5 71.70388182755067 45.000000000000014 49.999999999999986