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