CodeForces 343D Water Tree

Description

Mad scientist Mike has constructed a rooted tree, which consists of n

The vertices of the tree are numbered from 1 to n

Mike wants to do the following operations with the tree:

1. Fill vertex v with water. Then v
2. Empty vertex v. Then v
3. Determine whether vertex v

Initially all vertices of the tree are empty.

Mike has already compiled a full list of operations that he wants to perform in order. Before experimenting with the tree Mike decided to run the list through a simulation. Help Mike determine what results will he get after performing all the operations.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 500000) — the number of vertices in the tree. Each of the following n - 1lines contains two space-separated numbers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the edges of the tree.

The next line contains a number q (1 ≤ q ≤ 500000) — the number of operations to perform. Each of the following q lines contains two space-separated numbers ci (1 ≤ ci ≤ 3), vi (1 ≤ vi ≤ n), where ci is the operation type (according to the numbering given in the statement), and vi

It is guaranteed that the given graph is a tree.

Output

For each type 3 operation print 1 on a separate line if the vertex is full, and 0 if the vertex is empty. Print the answers to queries in the order in which the queries are given in the input.

Sample Input

Input

5
1 2
5 1
2 3
4 2
12
1 1
2 3
3 1
3 2
3 3
3 4
1 2
2 4
3 1
3 3
3 4
3 5      

Output

1

1

1

樹鍊剖分+線段樹，維護一棵線段樹，樹鍊剖分的特性可以滿足題目中從節點到根的指派的操作，

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])
#define inone(x) scanf("%d",&x)
#define intwo(x,y) scanf("%d%d",&x,&y)
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
const int low(int x) { return x&-x; }
const int N = 1e6 + 10;
int n, m, x, y;
int ft[N], nt[N], u[N], sz;
int ct[N], mx[N], fa[N];
int dep[N], top[N], L[N], R[N];
int f[N << 1];

void dfs(int x, int f)
{
  ct[x] = 1; mx[x] = 0;
  fa[x] = f; dep[x] = dep[f] + 1;
  loop(i, ft[x], nt)
  {
    if (u[i] == f) continue;
    dfs(u[i], x);
    ct[x] += ct[u[i]];
    if (ct[u[i]] > ct[mx[x]]) mx[x] = u[i];
  }
}

void Dfs(int x, int t)
{
  top[x] = !t ? x : top[fa[x]];
  L[x] = ++sz;
  if (mx[x]) Dfs(mx[x], 1);
  loop(i, ft[x], nt)
  {
    if (u[i] == fa[x] || u[i] == mx[x]) continue;
    Dfs(u[i], 0);
  }
  R[x] = sz;
}

void build(int x, int l, int r)
{
  if (l == r) { f[x] = -1; return; }
  int mid = l + r >> 1;
  f[x] = 0; build(lson); build(rson);
}

void add(int x, int l, int r, int ll, int rr, int t)
{
  if (ll <= l&&r <= rr) f[x] = t;
  else
  {
    int mid = l + r >> 1;
    if (f[x]) f[x << 1] = f[x << 1 | 1] = f[x], f[x] = 0;
    if (ll <= mid) add(lson, ll, rr, t);
    if (rr > mid) add(rson, ll, rr, t);
  }
}

int find(int x, int l, int r, int u)
{
  if (f[x]) return max(f[x], 0);
  int mid = l + r >> 1;
  if (u <= mid) return find(lson, u);
  else return find(rson, u);
}

int main()
{
  while (inone(n) != EOF)
  {
    rep(i, 1, n) ft[i] = -1;
    ct[0] = dep[0] = sz = 0;
    rep(i, 1, n - 1)
    {
      intwo(x, y);
      u[sz] = y; nt[sz] = ft[x]; ft[x] = sz++;
      u[sz] = x; nt[sz] = ft[y]; ft[y] = sz++;
    }
    dfs(1, sz = 0); Dfs(1, 0);
    build(1, 1, n);
    inone(m);
    while (m--)
    {
      intwo(x, y);
      if (x == 1) add(1, 1, n, L[y], R[y], 1);
      else if (x == 2)
      {
        for (int i = y; i; i = fa[top[i]]) add(1, 1, n, L[top[i]], L[i], -1);
      }
      else printf("%d\n", find(1, 1, n, L[y]));
    }
  }
  return 0;
}