Prime Distance On Tree
All submissions for this problem are available.
Problem description.You are given a tree. If we select 2 distinct nodes uniformly at random, what's the probability that the distance between these 2 nodes is a prime number?
InputThe first line contains a number N: the number of nodes in this tree. The following N-1 lines contain pairs a[i] and b[i], which means there is an edge with length 1 between a[i] and b[i].
OutputOutput a real number denote the probability we want. You'll get accept if the difference between your answer and standard answer is no more than 10^-6.
Constraints2 ≤ N ≤ 50,000
The input must be a tree.
Input: 5 1 2 2 3 3 4 4 5 Output: 0.5
ExplanationWe have C(5, 2) = 10 choices, and these 5 of them have a prime distance:
1-3, 2-4, 3-5: 2
1-4, 2-5: 3
Note that 1 is not a prime number.
|Tags||aug13, cgy4ever, dfs, fft, graph, hard|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.