Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- @SuppressWarnings("unchecked")
- public class deleg {
- static ArrayList<Integer>[] adj;
- static boolean[] visited;
- static int[] prev; // stores the parent of each node
- static int[] dp;
- static boolean[] done;
- static int REEEE = -196342;
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new FileReader("deleg.in"));
- PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("deleg.out")));
- StringTokenizer st = new StringTokenizer(br.readLine());
- int n = Integer.parseInt(st.nextToken());
- adj = new ArrayList[n];
- visited = new boolean[n];
- prev = new int[n]; Arrays.fill(prev, -1);
- dp = new int[n]; Arrays.fill(dp, -1);
- done = new boolean[n];
- for(int i = 0; i < n; i++){
- adj[i] = new ArrayList<Integer>();
- }
- for(int i = 0; i < n-1; i++){
- st = new StringTokenizer(br.readLine());
- int a = Integer.parseInt(st.nextToken())-1;
- int b = Integer.parseInt(st.nextToken())-1;
- adj[a].add(b);
- adj[b].add(a);
- }
- dfs2(0);
- int[] ans = new int[n];
- for(int i = 1; i <= n-1; i++){
- if((n-1) % i != 0){
- ans[i] = 0;
- } else {
- ans[i] = (dfs(0, i) == 0) ? 1 : 0;
- }
- }
- for(int i = 1; i <= n-1; i++){
- pw.print(ans[i]);
- }
- br.close();
- pw.close();
- }
- static void dfs2(int start){
- for(int e : adj[start]){
- if(e == prev[start]){ continue; }
- else{
- prev[e] = start;
- dfs2(e);
- }
- }
- }
- static int dfs(int start, int k){
- int ret = 0;
- int bad = 0; // number of bad child nodes that can't be matched
- int[] res = new int[k];
- if(adj[start].size() == 1 && start != 0){
- return 0;
- }
- for(int next : adj[start]){
- if(next == prev[start]){ continue; } // bad
- else{
- int x = 1 + dfs(next, k);
- if(x < 0){
- return REEEE;
- }
- res[x % k]++;
- }
- }
- if(k % 2 == 0){
- for(int i = 1; i <= (k/2)-1; i++){
- int worse = Math.abs(res[i] - res[k-i]);
- bad += worse;
- if(worse == 1){
- if(res[i] > res[k-i]){
- ret += i;
- } else {
- ret += (k-i);
- }
- }
- }
- int worst = res[k/2] % 2;
- if(worst == 1){
- ret += (k/2);
- }
- bad += worst;
- } else {
- for(int i = 1; i <= (k/2); i++){
- int worse = Math.abs(res[i] - res[k-i]);
- bad += worse;
- if(worse == 1){
- if(res[i] > res[k-i]){
- ret += i;
- } else {
- ret += (k-i);
- }
- }
- }
- }
- if(bad > 1){
- return REEEE;
- } else if(bad == 1){
- return ret;
- } else{
- return 0;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement