fork(5) download
copy 
  1. import java.io.OutputStreamWriter;
  2. import java.io.BufferedWriter;
  3. import java.io.OutputStream;
  4. import java.io.PrintWriter;
  5. import java.io.Writer;
  6. import java.util.List;
  7. import java.io.IOException;
  8. import java.util.Arrays;
  9. import java.util.InputMismatchException;
  10. import java.util.ArrayList;
  11. import java.util.NoSuchElementException;
  12. import java.math.BigInteger;
  13. import java.io.InputStream;
  14.  
  15. /**
  16.   @author Anuj Rana
  17.  */
  18. public class Main {
  19.     public static void main(String[] args) {
  20. 		InputStream inputStream = System.in;
  21. 		OutputStream outputStream = System.out;
  22. 		InputReader in = new InputReader(inputStream);
  23. 		OutputWriter out = new OutputWriter(outputStream);
  24.  
  25. 		CLASSNAME solver = new CLASSNAME();
  26.  
  27. 		solver.solve(1, in, out);
  28. 		out.close();
  29. 	}
  30. }
  31.  
  32. class CLASSNAME {
  33. 	static long total=0;
  34.     public void solve(int testNumber, InputReader in, OutputWriter out) {
  35.     	int n=in.readInt();
  36.     	boolean[][] tree=new boolean[n+1][n+1];
  37.     	//ArrayList<Integer> primes=new ArrayList<Integer>(IntegerUtils.generatePrimes(n));
  38.     	boolean[] isPrime=IntegerUtils.generatePrimalityTable(100001);
  39.     	for(int i=1;i<n;i++)
  40.     		tree[in.readInt()][in.readInt()]=true;
  41.  
  42.     	for(int i=1;i<n;i++){
  43.     		recurse(tree,isPrime,1,i);
  44.     	}
  45.     //	out.printLine(isPrime[2]);
  46.     //	out.printLine(total);
  47.     	out.printLine(total/((n*(n-1))/2.0));
  48.     }
  49.     static void recurse(boolean[][] tree,boolean[] isPrime,int sum,int level){
  50.     	if(level>=tree[0].length)return;
  51.     	for(int i=1;i<tree[0].length;i++){
  52.     		if(tree[level][i]){
  53.     			if(isPrime[sum]){
  54.     				total++;
  55.     				//System.out.println(level+" "+i);
  56.     			}
  57.     			recurse(tree,isPrime,sum+1,i);
  58.     		}
  59.     	}
  60.     }
  61. }
  62.  
  63. class InputReader {
  64.  
  65. 	private InputStream stream;
  66. 	private byte[] buf = new byte[1024];
  67. 	private int curChar;
  68. 	private int numChars;
  69. 	private SpaceCharFilter filter;
  70.  
  71. 	public InputReader(InputStream stream) {
  72. 		this.stream = stream;
  73. 	}
  74.  
  75. 	public int read() {
  76. 		if (numChars == -1)
  77. 			throw new InputMismatchException();
  78. 		if (curChar >= numChars) {
  79. 			curChar = 0;
  80. 			try {
  81. 				numChars = stream.read(buf);
  82. 			} catch (IOException e) {
  83. 				throw new InputMismatchException();
  84. 			}
  85. 			if (numChars <= 0)
  86. 				return -1;
  87. 		}
  88. 		return buf[curChar++];
  89. 	}
  90.  
  91. 	public int readInt() {
  92. 		int c = read();
  93. 		while (isSpaceChar(c))
  94. 			c = read();
  95. 		int sgn = 1;
  96. 		if (c == '-') {
  97. 			sgn = -1;
  98. 			c = read();
  99. 		}
  100. 		int res = 0;
  101. 		do {
  102. 			if (c < '0' || c > '9')
  103. 				throw new InputMismatchException();
  104. 			res *= 10;
  105. 			res += c - '0';
  106. 			c = read();
  107. 		} while (!isSpaceChar(c));
  108. 		return res * sgn;
  109. 	}
  110.  
  111. 	public boolean isSpaceChar(int c) {
  112. 		if (filter != null)
  113. 			return filter.isSpaceChar(c);
  114. 		return isWhitespace(c);
  115. 	}
  116.  
  117. 	public static boolean isWhitespace(int c) {
  118. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  119. 	}
  120.  
  121. 	public interface SpaceCharFilter {
  122. 		public boolean isSpaceChar(int ch);
  123. 	}
  124. }
  125.  
  126. class OutputWriter {
  127. 	private final PrintWriter writer;
  128.  
  129. 	public OutputWriter(OutputStream outputStream) {
  130. 		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  131. 	}
  132.  
  133. 	public OutputWriter(Writer writer) {
  134. 		this.writer = new PrintWriter(writer);
  135. 	}
  136.  
  137. 	public void print(Object...objects) {
  138. 		for (int i = 0; i < objects.length; i++) {
  139. 			if (i != 0)
  140. 				writer.print(' ');
  141. 			writer.print(objects[i]);
  142. 		}
  143. 	}
  144.  
  145.     public void printLine(Object...objects) {
  146. 		print(objects);
  147. 		writer.println();
  148. 	}
  149.  
  150. 	public void close() {
  151. 		writer.close();
  152. 	}
  153.  
  154. 	}
  155.  
  156. class IOUtils {
  157.  
  158. 	public static int[] readIntArray(InputReader in, int size) {
  159. 		int[] array = new int[size];
  160. 		for (int i = 0; i < size; i++)
  161. 			array[i] = in.readInt();
  162. 		return array;
  163. 	}
  164.  
  165. 	}
  166.  
  167. class IntegerUtils {
  168.  
  169.     public static int[] generatePrimes(int upTo) {
  170. 		boolean[] isPrime = generatePrimalityTable(upTo);
  171. 		IntList primes = new IntArrayList();
  172. 		for (int i = 0; i <= upTo; i++) {
  173. 			if (isPrime[i])
  174. 				primes.add(i);
  175. 		}
  176. 		return primes.toArray();
  177. 	}
  178.  
  179. 	public static boolean[] generatePrimalityTable(int upTo) {
  180. 		boolean[] isPrime = new boolean[upTo+1];
  181. 		Arrays.fill(isPrime, true);
  182. 		isPrime[0] = isPrime[1] = false;
  183. 		for (int i = 2; i * i <= upTo; i++) {
  184. 			if (isPrime[i]) {
  185. 				for (int j = i * i; j <= upTo; j += i)
  186. 					isPrime[j] = false;
  187. 			}
  188. 		}
  189. 		return isPrime;
  190. 	}
  191.  
  192. 	public static long power(long base, long exponent, long mod) {
  193. 		if (base >= mod)
  194. 			base %= mod;
  195. 		if (exponent == 0)
  196. 			return 1 % mod;
  197. 		long result = power(base, exponent >> 1, mod);
  198. 		result = result * result % mod;
  199. 		if ((exponent & 1) != 0)
  200. 			result = result * base % mod;
  201. 		return result;
  202. 	}
  203.  
  204. 	}
  205.  
  206. abstract class IntCollection {
  207. 	public abstract IntIterator iterator();
  208. 	public abstract int size();
  209. 	public abstract void add(int value);
  210.  
  211. 	public int[] toArray() {
  212. 		int size = size();
  213. 		int[] array = new int[size];
  214. 		int i = 0;
  215. 		for (IntIterator iterator = iterator(); iterator.isValid(); iterator.advance())
  216. 			array[i++] = iterator.value();
  217. 		return array;
  218. 	}
  219.  
  220. 	public void addAll(IntCollection values) {
  221. 		for (IntIterator it = values.iterator(); it.isValid(); it.advance()) {
  222. 			add(it.value());
  223. 		}
  224. 	}
  225.  
  226. 	}
  227.  
  228. interface IntIterator {
  229. 	public int value() throws NoSuchElementException;
  230. 	/*
  231. 	 * @throws NoSuchElementException only if iterator already invalid
  232. 	 */
  233. 	public void advance() throws NoSuchElementException;
  234. 	public boolean isValid();
  235. }
  236.  
  237. abstract class IntList extends IntCollection implements Comparable<IntList> {
  238.  
  239. 	public abstract int get(int index);
  240.  
  241. 	public IntIterator iterator() {
  242. 		return new IntIterator() {
  243. 			private int size = size();
  244. 			private int index = 0;
  245.  
  246. 			public int value() throws NoSuchElementException {
  247. 				if (!isValid())
  248. 					throw new NoSuchElementException();
  249. 				return get(index);
  250. 			}
  251.  
  252. 			public void advance() throws NoSuchElementException {
  253. 				if (!isValid())
  254. 					throw new NoSuchElementException();
  255. 				index++;
  256. 			}
  257.  
  258. 			public boolean isValid() {
  259. 				return index < size;
  260. 			}
  261. 		};
  262. 	}
  263.  
  264. 	public int hashCode() {
  265. 		int hashCode = 1;
  266. 		for (IntIterator i = iterator(); i.isValid(); i.advance())
  267. 			hashCode = 31 * hashCode + i.value();
  268. 		return hashCode;
  269. 	}
  270.  
  271. 	public boolean equals(Object obj) {
  272. 		if (!(obj instanceof IntList))
  273. 			return false;
  274. 		IntList list = (IntList)obj;
  275. 		if (list.size() != size())
  276. 			return false;
  277. 		IntIterator i = iterator();
  278. 		IntIterator j = list.iterator();
  279. 		while (i.isValid()) {
  280. 			if (i.value() != j.value())
  281. 				return false;
  282. 			i.advance();
  283. 			j.advance();
  284. 		}
  285. 		return true;
  286. 	}
  287.  
  288. 	public int compareTo(IntList o) {
  289. 		IntIterator i = iterator();
  290. 		IntIterator j = o.iterator();
  291. 		while (true) {
  292. 			if (i.isValid()) {
  293. 				if (j.isValid()) {
  294. 					if (i.value() != j.value()) {
  295. 						if (i.value() < j.value())
  296. 							return -1;
  297. 						else
  298. 							return 1;
  299. 					}
  300. 				} else
  301. 					return 1;
  302. 			} else {
  303. 				if (j.isValid())
  304. 					return -1;
  305. 				else
  306. 					return 0;
  307. 			}
  308. 			i.advance();
  309. 			j.advance();
  310. 		}
  311. 	}
  312.  
  313. 	}
  314.  
  315. class IntArrayList extends IntList {
  316. 	private int[] array;
  317. 	private int size;
  318.  
  319. 	public IntArrayList() {
  320. 		this(10);
  321. 	}
  322.  
  323. 	public IntArrayList(int capacity) {
  324. 		array = new int[capacity];
  325. 	}
  326.  
  327. 	public IntArrayList(IntList list) {
  328. 		this(list.size());
  329. 		addAll(list);
  330. 	}
  331.  
  332. 	public int get(int index) {
  333. 		if (index >= size)
  334. 			throw new IndexOutOfBoundsException();
  335. 		return array[index];
  336. 	}
  337.  
  338. 	public int size() {
  339. 		return size;
  340. 	}
  341.  
  342. 	public void add(int value) {
  343. 		ensureCapacity(size + 1);
  344. 		array[size++] = value;
  345. 	}
  346.  
  347. 	public void ensureCapacity(int newCapacity) {
  348. 		if (newCapacity > array.length) {
  349. 			int[] newArray = new int[Math.max(newCapacity, array.length << 1)];
  350. 			System.arraycopy(array, 0, newArray, 0, size);
  351. 			array = newArray;
  352. 		}
  353. 	}
  354.  
  355. 	public int[] toArray() {
  356. 		int[] array = new int[size];
  357. 		System.arraycopy(this.array, 0, array, 0, size);
  358. 		return array;
  359. 	}
  360.  
  361.     }
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
5
1 2
2 3
3 4
4 5
stdout
copy 
0.5
https://ideone.com/t9Lk6Z
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!