Advertisement
Guest User

Untitled

a guest
Aug 28th, 2016
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.70 KB | None | 0 0
  1. package main;
  2.  
  3. import java.util.*;
  4. import java.util.function.*;
  5. import static java.lang.Math.*;
  6.  
  7. public class Main {
  8.     public static class Solver {
  9.         Scanner in = new Scanner(System.in);
  10.  
  11.         <T> void println(T x) {
  12.             System.out.println(x);
  13.         }
  14.  
  15.         <T> void print(T x) {
  16.             System.out.print(x);
  17.         }
  18.  
  19.         void makeTree() {
  20.             boolean[] visited = new boolean[n + 1];
  21.             Queue<Integer> q = new ArrayDeque<>();
  22.             q.add(1);
  23.  
  24.             while (!q.isEmpty()) {
  25.                 int u = q.remove();
  26.                 visited[u] = true;
  27.  
  28.                 for (int v : g[u]) {
  29.                     if (!visited[v]) {
  30.                         children[u].add(v);
  31.                         q.add(v);
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.  
  37.         int n;
  38.  
  39.         ArrayList<Integer>[] g, children;
  40.         int[] sz, maxSep, maxSuptreeSep;
  41.  
  42.         interface Action {
  43.             void apply(int u);
  44.         }
  45.  
  46.         void applyRecursive(int start, Action action) {
  47.             boolean[] visited = new boolean[n + 1];
  48.             Stack<Integer> s = new Stack<>();
  49.             s.add(start);
  50.  
  51.             while (!s.isEmpty()) {
  52.                 int u = s.peek();
  53.                 visited[u] = true;
  54.  
  55.                 boolean rec = false;
  56.                 for (int v : children[u]) {
  57.                     if (!visited[v]) {
  58.                         s.push(v);
  59.                         rec = true;
  60.                     }
  61.                 }
  62.  
  63.                 if (!rec) {
  64.                     action.apply(u);
  65.                     s.pop();
  66.                 }
  67.             }
  68.         }
  69.  
  70.         void calcTreeSize() {
  71.             applyRecursive(1, u -> sz[u] = children[u].stream().mapToInt(v -> sz[v]).sum() + 1);
  72.         }
  73.  
  74.         void calcMaxSeparation() {
  75.             applyRecursive(1, u -> maxSep[u] = sz[u] <= n / 2
  76.                     ? sz[u]
  77.                     : children[u].stream().mapToInt(v -> maxSep[v]).max().getAsInt());
  78.         }
  79.  
  80.         void calcMaxSuptreeSeparation() {
  81.             Stack<Integer> s = new Stack<>();
  82.             s.add(1);
  83.  
  84.             while (!s.isEmpty()) {
  85.                 int u = s.pop();
  86.  
  87.                 if (children[u].size() == 0) continue;
  88.  
  89.                 int max1 = -1;
  90.                 int maxSize = -1;
  91.                 for (int v : children[u]) {
  92.                     if (maxSep[v] > maxSize) {
  93.                         maxSize = maxSep[v];
  94.                         max1 = v;
  95.                     }
  96.                 }
  97.  
  98.                 int max2 = -1;
  99.                 maxSize = -1;
  100.                 for (int v : children[u]) {
  101.                     if (v != max1 && maxSep[v] > maxSize) {
  102.                         maxSize = maxSep[v];
  103.                         max2 = v;
  104.                     }
  105.                 }
  106.  
  107.                 maxSize = n - sz[u] <= n / 2
  108.                         ? n - sz[u]
  109.                         : maxSuptreeSep[u];
  110.  
  111.                 for (int v : children[u]) {
  112.                     if (v == max1) {
  113.                         maxSuptreeSep[v] = max2 == -1
  114.                                 ? maxSize
  115.                                 : max(maxSize, maxSep[max2]);
  116.                     } else {
  117.                         maxSuptreeSep[v] = max(maxSize, maxSep[max1]);
  118.                     }
  119.                     s.push(v);
  120.                 }
  121.             }
  122.         }
  123.  
  124.         boolean isCentroid(int u) {
  125.             for (int v : children[u]) {
  126.                 if (sz[v] > n / 2) return sz[v] - maxSep[v] <= n / 2;
  127.             }
  128.  
  129.             if (n - sz[u] > n / 2) return n - sz[u] - maxSuptreeSep[u] <= n / 2;
  130.  
  131.             return true;
  132.         }
  133.  
  134.         void solve() {
  135.             n = in.nextInt();
  136.  
  137.             g = new ArrayList[n + 1];
  138.             children = new ArrayList[n + 1];
  139.             for (int v = 1; v <= n; v++) {
  140.                 g[v] = new ArrayList<>();
  141.                 children[v] = new ArrayList<>();
  142.             }
  143.  
  144.             for (int i = 0; i < n - 1; i++) {
  145.                 int u = in.nextInt();
  146.                 int v = in.nextInt();
  147.                 g[u].add(v);
  148.                 g[v].add(u);
  149.             }
  150.  
  151.             makeTree();
  152.  
  153.             sz = new int[n + 1];
  154.             calcTreeSize();
  155.  
  156.             maxSep = new int[n + 1];
  157.             calcMaxSeparation();
  158.  
  159.             maxSuptreeSep = new int[n + 1];
  160.             maxSuptreeSep[1] = -1;
  161.             calcMaxSuptreeSeparation();
  162.  
  163.             for (int v = 1; v <= n; v++) {
  164.                 print(isCentroid(v) ? '1' : '0');
  165.                 print(' ');
  166.             }
  167.         }
  168.     }
  169.  
  170.     public static void main(String[] args) {
  171.         new Solver().solve();
  172.     }
  173. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement