fork download
  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
stdin
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
Standard output is empty