{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003c/p\u003e \n\u003cdiv\u003e \n \u003ch3\u003e All submissions for this problem are available.\u003c/h3\u003e \n \u003ch3\u003e Problem description.\u003c/h3\u003e \n \u003cp\u003e You are given a tree. If we select 2 distinct nodes uniformly at random, what\u0027s the probability that the distance between these 2 nodes is a prime number?\u003c/p\u003e \n \u003ch3\u003e Input\u003c/h3\u003e \n \u003cp\u003e The first line contains a number\u0026nbsp;\u003cb\u003eN\u003c/b\u003e: the number of nodes in this tree.\u003cbr\u003e The following\u0026nbsp;\u003cb\u003eN\u003c/b\u003e-1 lines contain pairs a[i] and b[i], which means there is an edge with length 1 between a[i] and b[i].\u003c/p\u003e \n \u003ch3\u003e Output\u003c/h3\u003e \n \u003cp\u003e Output a real number denote the probability we want.\u003cbr\u003e You\u0027ll get accept if the difference between your answer and standard answer is no more than 10^-6.\u003c/p\u003e \n \u003ch3\u003e Constraints\u003c/h3\u003e \n \u003cp\u003e \u003cb\u003e2\u003c/b\u003e\u0026nbsp;≤\u0026nbsp;\u003cb\u003eN\u003c/b\u003e\u0026nbsp;≤\u0026nbsp;\u003cb\u003e50,000\u003c/b\u003e\u003cbr\u003e \u003cbr\u003e The input must be a tree.\u003c/p\u003e \n \u003ch3\u003e Example\u003c/h3\u003e \n \u003cpre\u003e\r\n\t\u003cb\u003eInput:\u003c/b\u003e\r\n5\r\n1 2\r\n2 3\r\n3 4\r\n4 5\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n0.5\r\n\u003c/pre\u003e \n \u003ch3\u003e Explanation\u003c/h3\u003e \n \u003cp\u003e We have C(5, 2) \u003d 10 choices, and these 5 of them have a prime distance:\u003cbr\u003e \u003cbr\u003e 1-3, 2-4, 3-5: 2\u003cbr\u003e \u003cbr\u003e 1-4, 2-5: 3\u003cbr\u003e \u003cbr\u003e Note that 1 is not a prime number.\u003c/p\u003e \n \u003ctable\u003e \n \u003ctbody\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Author:\u003c/td\u003e \n \u003ctd\u003e \u003ca href\u003d\"https://www.codechef.com/users/cgy4ever\"\u003ecgy4ever\u003c/a\u003e\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Tester:\u003c/td\u003e \n \u003ctd\u003e \u003ca href\u003d\"https://www.codechef.com/users/white_king\"\u003ewhite_king\u003c/a\u003e\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Editorial:\u003c/td\u003e \n \u003ctd\u003e \u003ca href\u003d\"http://discuss.codechef.com/problems/PRIMEDST\"\u003ehttp://discuss.codechef.com/problems/PRIMEDST\u003c/a\u003e\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Tags:\u003c/td\u003e \n \u003ctd\u003e \u003ca href\u003d\"https://www.codechef.com/tags/problems/aug13\"\u003eaug13\u0026nbsp;\u003c/a\u003e\u003ca href\u003d\"https://www.codechef.com/tags/problems/cgy4ever\"\u003ecgy4ever\u0026nbsp;\u003c/a\u003e\u003ca href\u003d\"https://www.codechef.com/tags/problems/dfs\"\u003edfs\u0026nbsp;\u003c/a\u003e\u003ca href\u003d\"https://www.codechef.com/tags/problems/fft\"\u003efft\u0026nbsp;\u003c/a\u003e\u003ca href\u003d\"https://www.codechef.com/tags/problems/graph\"\u003egraph\u0026nbsp;\u003c/a\u003e\u003ca href\u003d\"https://www.codechef.com/tags/problems/hard\"\u003ehard\u003c/a\u003e\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Date Added:\u003c/td\u003e \n \u003ctd\u003e 12-06-2013\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Time Limit:\u003c/td\u003e \n \u003ctd\u003e 5\u0026nbsp;sec\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Source Limit:\u003c/td\u003e \n \u003ctd\u003e 50000\u0026nbsp;Bytes\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"14%\"\u003e Languages:\u003c/td\u003e \n \u003ctd\u003e ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC\u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e \n \u003c/table\u003e \n\u003c/div\u003e \n\u003cul\u003e \n\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e \u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e \u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e \u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e \u003c/p\u003e"}}]}