fork(1) download
copy 
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.PrintWriter;
  6. import java.io.StreamTokenizer;
  7. import java.util.ArrayList;
  8.  
  9. public class WaterTree {
  10.  
  11.     static StreamTokenizer in;
  12.     static PrintWriter out;
  13.  
  14.     static int nextInt() throws IOException {
  15.         in.nextToken();
  16.         return (int) in.nval;
  17.     }
  18.     static final int MAXN = 500005;
  19.     static ArrayList<ArrayList<Integer>> G;
  20.     static int timer;
  21.     static int[] tin = new int[MAXN];
  22.     static int[] tout = new int[MAXN];
  23.     static int[] parent = new int[MAXN];
  24.  
  25.     static void dfs(int u, int p) {
  26.         parent[u] = p;
  27.         tin[u] = timer;
  28.         for (int v : G.get(u)) {
  29.             if (v != p) {
  30.                 dfs(v, u);
  31.             }
  32.         }
  33.         tout[u] = timer++;
  34.     }
  35.     static boolean[] T = new boolean[8 * MAXN];
  36.     static boolean[] promise = new boolean[8 * MAXN];
  37.  
  38.     static void build(int v, int tl, int tr) {
  39.         if (tl < tr) {
  40.             int tm = (tl + tr) / 2;
  41.             build(2 * v, tl, tm);
  42.             build(2 * v + 1, tm + 1, tr);
  43.         }
  44.         T[v] = true;
  45.     }
  46.  
  47.     static void push(int v) {
  48.         if (promise[v]) {
  49.             promise[v] = false;
  50.             promise[2 * v] = promise[2 * v + 1] = true;
  51.             T[2 * v] = T[2 * v + 1] = false;
  52.         }
  53.     }
  54.  
  55.     static boolean get(int l, int r, int v, int tl, int tr) {
  56.         if (l > r) {
  57.             return false;
  58.         }
  59.         push(v);
  60.         if (tl == l && tr == r) {
  61.             return T[v];
  62.         } else {
  63.             int tm = (tl + tr) / 2;
  64.             return get(l, Math.min(r, tm), 2 * v, tl, tm)
  65.                     || get(Math.max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);
  66.         }
  67.     }
  68.  
  69.     static void update(int p, int v, int tl, int tr) {
  70.         push(v);
  71.         T[v] = true;
  72.         if (tl < tr) {
  73.             int tm = (tl + tr) / 2;
  74.             if (p <= tm) {
  75.                 update(p, 2 * v, tl, tm);
  76.             } else {
  77.                 update(p, 2 * v + 1, tm + 1, tr);
  78.             }
  79.         }
  80.     }
  81.  
  82.     static void color(int l, int r, int v, int tl, int tr) {
  83.         if (l > r || promise[v]) {
  84.             return;
  85.         }
  86.         if (l == tl && r == tr) {
  87.             promise[v] = true;
  88.             T[v] = false;
  89.         } else {
  90.             int tm = (tl + tr) / 2;
  91.             color(l, Math.min(r, tm), 2 * v, tl, tm);
  92.             color(Math.max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);
  93.             T[v] = T[2 * v] || T[2 * v + 1];
  94.         }
  95.     }
  96.  
  97.     public static void main(String[] args) throws IOException {
  98.         in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  99.         out = new PrintWriter(System.out);
  100.  
  101.         int n = nextInt();
  102.         G = new ArrayList<ArrayList<Integer>>();
  103.         for (int i = 0; i < n; i++) {
  104.             G.add(new ArrayList<Integer>());
  105.         }
  106.         for (int i = 0; i < n - 1; i++) {
  107.             int a = nextInt() - 1;
  108.             int b = nextInt() - 1;
  109.             G.get(a).add(b);
  110.             G.get(b).add(a);
  111.         }
  112.  
  113.         timer = 0;
  114.         dfs(0, 0);
  115.         build(1, 0, n - 1);
  116.  
  117.         int q = nextInt();
  118.         for (int i = 0; i < q; i++) {
  119.             int c = nextInt();
  120.             int v = nextInt() - 1;
  121.             if (c == 1) {
  122.                 boolean up = get(tin[v], tout[v], 1, 0, n - 1);
  123.                 color(tin[v], tout[v], 1, 0, n - 1);
  124.                 if (up && v > 0) {
  125.                     update(tout[parent[v]], 1, 0, n - 1);
  126.                 }
  127.             } else if (c == 2) {
  128.                 update(tout[v], 1, 0, n - 1);
  129.             } else {
  130.                 out.println(get(tin[v], tout[v], 1, 0, n - 1) ? 0 : 1);
  131.             }
  132.         }
  133.         out.flush();
  134.     }
  135. }
  136.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:9: error: class WaterTree is public, should be declared in a file named WaterTree.java
public class WaterTree {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/5aNM4u
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!