记录编号	444180	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	4.009 s
提交时间	2017-09-02 11:43:12	内存使用	1.37 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAXN 30003
#define MAXM 10003
#define mid ((l + r) >> 1)
using namespace std;

inline char gc() { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
 
inline int gn() { 
    register char c;
    register int k = 0, f = 1;
    c = gc();
    for(; !isdigit(c); c = gc()) if(c == '-') f = -1;
    for(; isdigit(c); c = gc()) k = k * 10 + c - '0';
    return k * f;
}

int val[MAXN], dfn[MAXN], lev[MAXN], n, q, cnt;
vector<int> to[MAXN];

void dfs(int x) {
    dfn[x] = ++cnt;
    for(int i = 0; i < to[x].size(); i++) {
        if(dfn[to[x][i]]) continue;
        dfs(to[x][i]);
    }
    lev[x] = cnt;
}

struct node {
    int cnt;
    node *ls, *rs;
    node() {
        cnt = 0, ls = rs = NULL;
    }
}*root[MAXN];

void insert(node *&x, int l, int r, int v, int k) {
    if(!x) x = new node();
    x->cnt += k;
    if(l == r) return;
    if(v > mid) insert(x->rs, mid + 1, r, v, k);
    else insert(x->ls, l, mid, v, k);
}

int query(node *x, int l, int r, int s, int t) {
    if(!x) return 0;
    if(l == s && r == t) return x->cnt;
    if(t <= mid) return query(x->ls, l, mid, s, t);
    if(s > mid)  return query(x->rs, mid + 1, r, s, t);
    return query(x->ls, l, mid, s, mid) + query(x->rs, mid + 1, r, mid + 1, t);
}

inline int lb(int x) {
    return x & -x;
}

inline void add(int x, int v, int k) {
    for(; x <= n; x += lb(x)) insert(root[x], 1, MAXM, v, k);
}

inline int search(int s, int t, int l, int r) {
    int res = 0;
    for(; t; t -= lb(t)) res += query(root[t], 1, MAXM, l, r);
    for(s--; s; s-= lb(s)) res -= query(root[s], 1, MAXM, l, r);
    return res;
}

#undef mid

inline int kth(int x, int k) {
    int l = dfn[x], r = lev[x];
    int lv = 1, rv = MAXM, mid = (lv + rv) >> 1, ans, tmp;
    while(lv <= rv && (mid = (lv + rv) >> 1)) {
        if(search(l, r, 1, mid) >= k) {
            rv = (ans = mid) - 1;
        } else lv = mid + 1;
    }
    return ans;
}

int main(int argc, char const *argv[]) {
//#define LOCAL
#ifdef LOCAL 
    freopen("in", "r", stdin);
#else
    freopen("hjtree.in", "r", stdin);
    freopen("hjtree.out", "w", stdout);
#endif
    n = gn();
    for(int i = 1; i <= n; i++) {
        val[i] = gn();
    }
    for(int a, b, i = 1; i < n; i++) {
        a = gn(), b = gn();
        to[a].push_back(b);
        to[b].push_back(a);
    }
    dfs(1);
    for(int i = 1; i <= n; i++) add(dfn[i], val[i], 1);
    q = gn();
    int op, a, b, c;
    while(q--) {
        op = gn();
        if(op == 1) {
            a = gn(), b = gn();
            printf("%d\n", kth(a, b));
        } 
        else if(op == 2) {
            a = gn(), b = gn(), c = gn();
            printf("%d\n", search(dfn[a], lev[a], b, c));
        } 
        else {
            a = gn(), b = gn();
            add(dfn[a], val[a], -1);
            val[a] = b;
            add(dfn[a], val[a], +1);
        }
    }
    return 0;
}