fork download
copy 
  1. package CF630;
  2.  
  3. import java.io.IOException;
  4. import java.io.InputStream;
  5. import java.io.PrintWriter;
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.HashMap;
  9. import java.util.InputMismatchException;
  10.  
  11. public class F {
  12. 	private static int n;
  13. 	private static HashMap<Integer, ArrayList<Integer>> g;
  14. 	private static long ans = 0;
  15. //	private static final int MOD = 998244353;
  16.  
  17. 	public static void main(String[] args) {
  18. 		n = ini();
  19. 		g = new HashMap<>();
  20. 		for(int i=0; i<n; i++) {
  21. 			g.put(i, new ArrayList<>());
  22. 		}
  23. 		for(int i=0; i<n-1; i++) {
  24. 			int u = ini()-1;
  25. 			int v = ini()-1;
  26. 			g.get(u).add(v);
  27. 			g.get(v).add(u);
  28. 		}
  29.  
  30. 		println((dfs(0, -1, 0, 0)-1));
  31.  
  32.  
  33. 		out.flush();
  34. 		out.close();
  35.  
  36. 	}
  37.  
  38.  
  39. 	private static long dfs(int u, int p, int ps, int plink) {
  40. 		//solve for subtree rooted at u with parent p such that p is colored if ps
  41. 		//and p is linked to u if plink
  42.  
  43. 		long ans = 1;
  44.  
  45. 		for(int v: g.get(u)) {
  46. 			if (v==p) continue;
  47. 			if (plink==1) {
  48. 				if (ps==0) {
  49. 					ans = (ans*(dfs(v, u, 0, 0)+dfs(v, u, 1, 1)+dfs(v, u, 0, 0)+dfs(v, u, 0, 1)));
  50. 				} else {
  51. 					ans = (ans*(dfs(v, u, 0, 0)+dfs(v, u, 0, 1)));
  52. 				}
  53. 			} else {
  54. 				ans = (ans*(dfs(v, u, 1, 1)+dfs(v, u, 0, 1)+dfs(v, u, 0, 0)));
  55. 			}
  56.  
  57. 		}
  58.  
  59. 		return ans;
  60. 	}
  61.  
  62. 	//NONPROBLEM CODE
  63.  
  64. 	private static InputReader in = new InputReader(System.in);
  65. 	private static PrintWriter out = new PrintWriter(System.out);
  66.  
  67. 	private static class InputReader {
  68.  
  69. 		private final InputStream stream;
  70. 		private final byte[] buf = new byte[8192];
  71. 		private int curChar, snumChars;
  72.  
  73. 		public InputReader(InputStream st) {
  74. 			this.stream = st;
  75. 		}
  76.  
  77. 		public int read() {
  78. 			if (snumChars == -1)
  79. 				throw new InputMismatchException();
  80. 			if (curChar >= snumChars) {
  81. 				curChar = 0;
  82. 				try {
  83. 					snumChars = stream.read(buf);
  84. 				} catch (IOException e) {
  85. 					throw new InputMismatchException();
  86. 				}
  87. 				if (snumChars <= 0)
  88. 					return -1;
  89. 			}
  90. 			return buf[curChar++];
  91. 		}
  92.  
  93. 		public int nextInt() {
  94. 			int c = read();
  95. 			while (isSpaceChar(c)) {
  96. 				c = read();
  97. 			}
  98. 			int sgn = 1;
  99. 			if (c == '-') {
  100. 				sgn = -1;
  101. 				c = read();
  102. 			}
  103. 			int res = 0;
  104. 			do {
  105. 				res *= 10;
  106. 				res += c - '0';
  107. 				c = read();
  108. 			} while (!isSpaceChar(c));
  109. 			return res * sgn;
  110. 		}
  111.  
  112. 		public long nextLong() {
  113. 			int c = read();
  114. 			while (isSpaceChar(c)) {
  115. 				c = read();
  116. 			}
  117. 			int sgn = 1;
  118. 			if (c == '-') {
  119. 				sgn = -1;
  120. 				c = read();
  121. 			}
  122. 			long res = 0;
  123. 			do {
  124. 				res *= 10;
  125. 				res += c - '0';
  126. 				c = read();
  127. 			} while (!isSpaceChar(c));
  128. 			return res * sgn;
  129. 		}
  130.  
  131. 		public int[] nextIntArray(int n) {
  132. 			int a[] = new int[n];
  133. 			for (int i = 0; i < n; i++) {
  134. 				a[i] = nextInt();
  135. 			}
  136. 			return a;
  137. 		}
  138.  
  139. 		public String readString() {
  140. 			int c = read();
  141. 			while (isSpaceChar(c)) {
  142. 				c = read();
  143. 			}
  144. 			StringBuilder res = new StringBuilder();
  145. 			do {
  146. 				res.appendCodePoint(c);
  147. 				c = read();
  148. 			} while (!isSpaceChar(c));
  149. 			return res.toString();
  150. 		}
  151.  
  152. 		public String nextLine() {
  153. 			int c = read();
  154. 			while (isSpaceChar(c))
  155. 				c = read();
  156. 			StringBuilder res = new StringBuilder();
  157. 			do {
  158. 				res.appendCodePoint(c);
  159. 				c = read();
  160. 			} while (!isEndOfLine(c));
  161. 			return res.toString();
  162. 		}
  163.  
  164. 		public boolean isSpaceChar(int c) {
  165. 			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  166. 		}
  167.  
  168. 		private boolean isEndOfLine(int c) {
  169. 			return c == '\n' || c == '\r' || c == -1;
  170. 		}
  171.  
  172. 	}
  173.  
  174. 	//INPUT SHORTCUTS
  175.  
  176. 	private static int[] ina(int n) {
  177. 		int[] temp = new int[n];
  178. 		for (int i = 0; i < n; i++) {
  179. 			temp[i] = in.nextInt();
  180. 		}
  181. 		return temp;
  182. 	}
  183.  
  184. 	private static int ini() {
  185. 		return in.nextInt();
  186. 	}
  187.  
  188. 	//OTHER SHORTCUTS
  189. 	public static void sort(int[] a) {
  190. 		Arrays.sort(a);
  191. 	}
  192.  
  193. 	//PRINT SHORTCUTS
  194.  
  195. 	private static void println(Object... o) {
  196. 		for (Object x : o) {
  197. 			out.write(x + " ");
  198. 		}
  199. 		out.write("\n");
  200. 		out.flush();
  201. 	}
  202.  
  203. 	private static void print(Object... o) {
  204. 		for (Object x : o) {
  205. 			out.write(x + " ");
  206. 		}
  207. 		out.flush();
  208. 	}
  209.  
  210. 	private static void debug(Object... o) {
  211. 		for (Object x : o) {
  212. 			out.write(x + " ");
  213. 		}
  214. 		out.write("\n");
  215. 		out.flush();
  216. 	}
  217. }
  218.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:11: error: class F is public, should be declared in a file named F.java
public class F {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/zhB5cl
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

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!