记录编号	373416	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	5.716 s
提交时间	2017-02-21 06:58:32	内存使用	1.36 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
  inline int read_string(char *str){
    int len = 1;char c;
    while(!isalpha(c = readc()));str[0] = c;
    while(isalpha(c = readc()))str[len++] = c;
    str[len] = 0;
    return len;
  }
};using IO::read_string; using IO::readint;
#define MAXN 30001
#define MAXS 10000
vector<int> G[MAXN];
int dfs_time;
int dfn[MAXN]; //节点的dfs序。
int leave[MAXN]; //离开的时候的dfs序
void dfs(int u, int f){
  dfn[u] = ++dfs_time;
  for(int i = 0; i < G[u].size(); i++){
    int to = G[u][i]; if(to == f)continue;
    dfs(to, u);
  }
  leave[u] = dfs_time;
}
struct node{
  node *ls, *rs;
  int cnt;
};
node *new_node(){
  node *d = new node();
  memset(d, 0, sizeof(node));
  return d;
}
void insert(node *&x, int p, int d, int L, int R){
  if(!x)x = new_node();
  x->cnt += d;
  if(L < R){
    int M = (L+R)>>1;
    if(p <= M)insert(x->ls, p, d, L, M);
    if(p > M)insert(x->rs, p, d, M+1, R);
  }
}
int query(node *x, int l, int r, int L, int R){
  if(!x)return 0;
  if(l <= L && R <= r)return x->cnt;
  int M = (L+R)>>1, ret = 0;
  if(l <= M)ret += query(x->ls, l, r, L, M);
  if(r > M)ret += query(x->rs, l, r, M+1, R);
  return ret;
}
node *bit[MAXN];
int n;
int L_LIMIT = 1, R_LIMIT = MAXS;
void add(int p, int v, int d){
  for(; p <= n; p += p&-p)insert(bit[p], v, d, L_LIMIT, R_LIMIT);
}
int query(int l, int r, int vl, int vr){
  int ret = 0;
  for(; r; r -= r&-r)ret += query(bit[r], vl, vr, L_LIMIT, R_LIMIT);
  for(l--; l; l -= l&-l)ret -= query(bit[l], vl, vr, L_LIMIT, R_LIMIT);
  return ret;
}
int kth(int u, int k){ //以u为根的子树第k小
  int pl = dfn[u], pr = leave[u];
  int x = L_LIMIT, y = R_LIMIT;
  int ans = 0;
  while(x <= y){
    int m = (x+y)>>1;
    if(query(pl, pr, L_LIMIT, m) >= k){
      y = m-1;
      ans = m;
    }else x = m+1;
  }
  return ans;
}
int val[MAXN];
int main(){
  freopen("hjtree.in", "r", stdin);
  freopen("hjtree.out", "w", stdout);
  n = readint();
  for(int i = 1; i <= n; i++)val[i] = readint();
  for(int i = 1, u, v; i < n; i++){
    u = readint(); v = readint();
    G[u].push_back(v); G[v].push_back(u);
  }
  dfs(1, 0);
  for(int i = 1; i <= n; i++)add(dfn[i], val[i], 1);
  int q = readint();
  while(q--){
    int op = readint();
    if(op == 1){
      int u = readint(); int k = readint(); 
      printf("%d\n", kth(u, k));
    }else if(op == 2){
      int u = readint(); int a = readint(); int b = readint(); 
      printf("%d\n", query(dfn[u], leave[u], a, b));
    }else{
      int u = readint(); int x = readint();
      add(dfn[u], val[u], -1); add(dfn[u], val[u] = x, 1);
    }
  }
  return 0;
}