Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.41 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. @SuppressWarnings("unchecked")
  5. public class deleg {
  6.  
  7. static ArrayList<Integer>[] adj;
  8. static boolean[] visited;
  9. static int[] prev; // stores the parent of each node
  10. static int[] dp;
  11. static boolean[] done;
  12. static int REEEE = -196342;
  13. public static void main(String[] args) throws IOException {
  14. BufferedReader br = new BufferedReader(new FileReader("deleg.in"));
  15. PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("deleg.out")));
  16.  
  17. StringTokenizer st = new StringTokenizer(br.readLine());
  18. int n = Integer.parseInt(st.nextToken());
  19. adj = new ArrayList[n];
  20. visited = new boolean[n];
  21. prev = new int[n]; Arrays.fill(prev, -1);
  22. dp = new int[n]; Arrays.fill(dp, -1);
  23. done = new boolean[n];
  24. for(int i = 0; i < n; i++){
  25. adj[i] = new ArrayList<Integer>();
  26. }
  27. for(int i = 0; i < n-1; i++){
  28. st = new StringTokenizer(br.readLine());
  29. int a = Integer.parseInt(st.nextToken())-1;
  30. int b = Integer.parseInt(st.nextToken())-1;
  31. adj[a].add(b);
  32. adj[b].add(a);
  33. }
  34. dfs2(0);
  35. int[] ans = new int[n];
  36. for(int i = 1; i <= n-1; i++){
  37. if((n-1) % i != 0){
  38. ans[i] = 0;
  39. } else {
  40. ans[i] = (dfs(0, i) == 0) ? 1 : 0;
  41. }
  42. }
  43. for(int i = 1; i <= n-1; i++){
  44. pw.print(ans[i]);
  45. }
  46.  
  47. br.close();
  48. pw.close();
  49. }
  50.  
  51. static void dfs2(int start){
  52. for(int e : adj[start]){
  53. if(e == prev[start]){ continue; }
  54. else{
  55. prev[e] = start;
  56. dfs2(e);
  57. }
  58. }
  59. }
  60.  
  61. static int dfs(int start, int k){
  62. int ret = 0;
  63. int bad = 0; // number of bad child nodes that can't be matched
  64. int[] res = new int[k];
  65. if(adj[start].size() == 1 && start != 0){
  66. return 0;
  67. }
  68. for(int next : adj[start]){
  69. if(next == prev[start]){ continue; } // bad
  70. else{
  71. int x = 1 + dfs(next, k);
  72. if(x < 0){
  73. return REEEE;
  74. }
  75. res[x % k]++;
  76. }
  77. }
  78. if(k % 2 == 0){
  79. for(int i = 1; i <= (k/2)-1; i++){
  80. int worse = Math.abs(res[i] - res[k-i]);
  81. bad += worse;
  82. if(worse == 1){
  83. if(res[i] > res[k-i]){
  84. ret += i;
  85. } else {
  86. ret += (k-i);
  87. }
  88. }
  89. }
  90. int worst = res[k/2] % 2;
  91. if(worst == 1){
  92. ret += (k/2);
  93. }
  94. bad += worst;
  95. } else {
  96. for(int i = 1; i <= (k/2); i++){
  97. int worse = Math.abs(res[i] - res[k-i]);
  98. bad += worse;
  99. if(worse == 1){
  100. if(res[i] > res[k-i]){
  101. ret += i;
  102. } else {
  103. ret += (k-i);
  104. }
  105. }
  106. }
  107. }
  108. if(bad > 1){
  109. return REEEE;
  110. } else if(bad == 1){
  111. return ret;
  112. } else{
  113. return 0;
  114. }
  115. }
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement