In computer science, there is a method called "Divide And Conquer By Node" to solve some hard problems about paths on a tree. Let's desribe how this method works by function: solve(t) ( t is a tree): Chose a node x (it's common to chose weight-center) in tree t . Let's call this step "Line A". Deal with all paths that pass x . Then delete x from tree t . After that t becomes some subtrees. Apply solve on each subtree. This ends when t has only one node because after deleting it, there's nothing. Now, WJMZBMR has mistakenly believed that it's ok to chose any node in "Line A". So he'll chose a node at random. To make the situation worse, he thinks a "tree" should have the same number of edges and nodes! So this procedure becomes like that. Let's define the variable totalCost . Initially the value of totalCost equal to 0. So, solve(t) (now t is a graph): totalCost = totalCost + (size of t). The operation "=" means assignment. (Size of t) means the number of nodes in t . Choose a node x in graph t at random (uniformly among all nodes of t ). Then delete x from graph t . After that t becomes some connected components. Apply solve on each component. He'll apply solve on a connected graph with n nodes and n edges. He thinks it will work quickly, but it's very slow. So he wants to know the expectation of totalCost of this procedure. Can you help him?
输入描述:
The first line contains an integer n (3 ≤ n ≤ 3000) — the number of nodes and edges in the graph. Each of the next n lines contains two space-separated integers ai, bi(0 ≤ ai, bi ≤ n - 1) indicating an edge between nodes ai and bi.Consider that the graph nodes are numbered from 0 to (n - 1). It's guaranteed that there are no self-loops, no multiple edges in that graph. It's guaranteed that the graph is connected.
输出描述:
Print a single real number — the expectation of totalCost. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
示例1
输入
5<br />3 4<br />2 3<br />2 4<br />0 4<br />1 2<br />3<br />0 1<br />1 2<br />0 2<br />5<br />0 1<br />1 2<br />2 0<br />3 0<br />4 1<br />
输出
13.166666666666666<br />6.000000000000000<br />13.166666666666666<br />
备注:
Consider the second example. No matter what we choose first, the totalCost will always be 3 + 2 + 1 = 6.
加载中...