Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main;
- import java.util.*;
- import java.util.function.*;
- import static java.lang.Math.*;
- public class Main {
- public static class Solver {
- Scanner in = new Scanner(System.in);
- <T> void println(T x) {
- System.out.println(x);
- }
- <T> void print(T x) {
- System.out.print(x);
- }
- void makeTree() {
- boolean[] visited = new boolean[n + 1];
- Queue<Integer> q = new ArrayDeque<>();
- q.add(1);
- while (!q.isEmpty()) {
- int u = q.remove();
- visited[u] = true;
- for (int v : g[u]) {
- if (!visited[v]) {
- children[u].add(v);
- q.add(v);
- }
- }
- }
- }
- int n;
- ArrayList<Integer>[] g, children;
- int[] sz, maxSep, maxSuptreeSep;
- interface Action {
- void apply(int u);
- }
- void applyRecursive(int start, Action action) {
- boolean[] visited = new boolean[n + 1];
- Stack<Integer> s = new Stack<>();
- s.add(start);
- while (!s.isEmpty()) {
- int u = s.peek();
- visited[u] = true;
- boolean rec = false;
- for (int v : children[u]) {
- if (!visited[v]) {
- s.push(v);
- rec = true;
- }
- }
- if (!rec) {
- action.apply(u);
- s.pop();
- }
- }
- }
- void calcTreeSize() {
- applyRecursive(1, u -> sz[u] = children[u].stream().mapToInt(v -> sz[v]).sum() + 1);
- }
- void calcMaxSeparation() {
- applyRecursive(1, u -> maxSep[u] = sz[u] <= n / 2
- ? sz[u]
- : children[u].stream().mapToInt(v -> maxSep[v]).max().getAsInt());
- }
- void calcMaxSuptreeSeparation() {
- Stack<Integer> s = new Stack<>();
- s.add(1);
- while (!s.isEmpty()) {
- int u = s.pop();
- if (children[u].size() == 0) continue;
- int max1 = -1;
- int maxSize = -1;
- for (int v : children[u]) {
- if (maxSep[v] > maxSize) {
- maxSize = maxSep[v];
- max1 = v;
- }
- }
- int max2 = -1;
- maxSize = -1;
- for (int v : children[u]) {
- if (v != max1 && maxSep[v] > maxSize) {
- maxSize = maxSep[v];
- max2 = v;
- }
- }
- maxSize = n - sz[u] <= n / 2
- ? n - sz[u]
- : maxSuptreeSep[u];
- for (int v : children[u]) {
- if (v == max1) {
- maxSuptreeSep[v] = max2 == -1
- ? maxSize
- : max(maxSize, maxSep[max2]);
- } else {
- maxSuptreeSep[v] = max(maxSize, maxSep[max1]);
- }
- s.push(v);
- }
- }
- }
- boolean isCentroid(int u) {
- for (int v : children[u]) {
- if (sz[v] > n / 2) return sz[v] - maxSep[v] <= n / 2;
- }
- if (n - sz[u] > n / 2) return n - sz[u] - maxSuptreeSep[u] <= n / 2;
- return true;
- }
- void solve() {
- n = in.nextInt();
- g = new ArrayList[n + 1];
- children = new ArrayList[n + 1];
- for (int v = 1; v <= n; v++) {
- g[v] = new ArrayList<>();
- children[v] = new ArrayList<>();
- }
- for (int i = 0; i < n - 1; i++) {
- int u = in.nextInt();
- int v = in.nextInt();
- g[u].add(v);
- g[v].add(u);
- }
- makeTree();
- sz = new int[n + 1];
- calcTreeSize();
- maxSep = new int[n + 1];
- calcMaxSeparation();
- maxSuptreeSep = new int[n + 1];
- maxSuptreeSep[1] = -1;
- calcMaxSuptreeSeparation();
- for (int v = 1; v <= n; v++) {
- print(isCentroid(v) ? '1' : '0');
- print(' ');
- }
- }
- }
- public static void main(String[] args) {
- new Solver().solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement