Description
zzsyz实验楼里面种了一棵滑稽树，只有滑稽之力达到大乘期的oier才能看到。虽然我们看不到，但是还是知道一些信息：
这真的是一棵树，由n个节点，n-1条边联通。一号滑稽果同时也是整棵滑稽树的树根。滑稽树上每个节点有一个滑稽果，每个滑稽果有它的重量。
雪甜甜公主是神犇当然看得到那棵滑稽树啦，现在她感兴趣的是这样三件事
1：滑稽树太大啦，雪甜甜公主有的时候只想知道，在以某一个滑稽果为根的子滑稽树里面，重量第k小的果子的重量是多少？
2：除了重量第k小的果子，雪甜甜还想知道以某个滑稽果为根的子滑稽树里面，重量在[a, b]这个范围内的滑稽果有多少个。
3：雪甜甜还喜欢吃滑稽果，但是吃完，原来滑稽果的位置上还会长出一个新的滑稽果，只是重量可能不一样。
Input
第一行一个正整数n，表示滑稽树有n个节点。
第二行n个正整数，分别描述1号，2号,,,，n号节点滑稽果的重量。
接下来n-1行，每行2个正整数u, v ∈ [1, n]，表示滑稽果u与滑稽果v之间有树枝连接。
接下来一个正整数q，表示雪甜甜有q次行动
之后q行，有这样3种形式
1 u k 雪甜甜公主询问以u为根的子滑稽树中，重量第k小的滑稽果的重量。
2 u a b 雪甜甜公主想知道，以u为根的子滑稽树中，重量在[a, b]范围内的滑稽果有多少个。
3 u x 雪甜甜公主吃掉了编号为u的滑稽果，但是在原位置上立刻长出来了一个重量为x的滑稽果。因为位置没有变，所以编号还是u。
Output
对于每次询问，输出结果。
Sample Input
5
3 4 6 1 2
1 2
1 3
3 4
3 5
7
1 1 4
2 1 1 5
3 4 5
1 1 4
2 3 3 6
3 5 7
1 3 3
Sample Output
4
4
5
2
7
Hint
样例提示：
数据的范围及提示：
N：
对于前35%的数据满足，N <= 5000
对于前50%的数据满足，N <= 10000
对于前100%的数据满足，N <= 30000
滑稽果的重量：对于100%d的数据满足 滑稽果的重量 <= 10000
询问：询问的个数Q：
对于前50%的数据满足 Q <= 10000
对于前100%的数据满足 Q <= 50000
对于前25%的数据，只有第一种询问。
对于前65%的数据，有第1，2种询问。
对于100%的数据第1，2，3种询问都存在。
对于前35%的数据，满足一个特殊的限制条件：每次询问的滑稽果u = 1保证询问k小重量的滑稽果的时候，k值∈ [1, 子树的节点数]
题解：
变样的整体二分,直接记录进出子树的时间戳就可以转化为区间问题,
值得注意的是查找[L,R]的个数 的地方很细节.
只有t[i].k>mid 时才可以统计,不能取等,不然就会被加入到q1 然后被重复统计
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=,M=,Q=M*+N;
const int INF=-2e8;
int head[N],num=;
struct Lin{
int next,to;
}b[N<<];
void init(int x,int y){
b[++num].next=head[x];
b[num].to=y;
head[x]=num;
}
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=(str<<)+(str<<)+ch-,ch=getchar();
return str;
}
int n,m,val[N];
struct node{
int ki,x,y,k,cnt,id;
}t[Q<<],q1[Q<<],q2[Q<<];
int dfn[N],last[N],dfns=,tot=;
void dfs(int x){
dfn[x]=++dfns;
for(int i=head[x];i;i=b[i].next){
if(!dfn[b[i].to])dfs(b[i].to);
}
last[x]=dfns;
}
int a[N],ans[M],Tree[N*];
void add(int sta,int ad){
for(int i=sta;i<=n;i+=(i&(-i)))Tree[i]+=ad;
}
int getsum(int sta){
int sum=;
for(int i=sta;i>=;i-=(i&(-i)))sum+=Tree[i];
return sum;
}
int l1,l2;
void count(int ll,int rr,int dl,int dr)
{
l1=l2=;
for(int i=ll;i<=rr;i++)
{
if(t[i].ki==)
{
t[i].cnt=getsum(t[i].y)-getsum(t[i].x-);
if(t[i].cnt>=t[i].k)q1[++l1]=t[i];
else t[i].k-=t[i].cnt,q2[++l2]=t[i];
}
else if(t[i].ki==)
{
if(t[i].k>dr)
ans[t[i].id]+=(getsum(t[i].y)-getsum(t[i].x-))*t[i].cnt,q2[++l2]=t[i];
else
q1[++l1]=t[i];
}
else
{
if(t[i].y<=dr)add(t[i].x,t[i].cnt),q1[++l1]=t[i];
else q2[++l2]=t[i];
}
}
for(int i=;i<=l1;i++)
if(q1[i].ki==)
add(q1[i].x,-q1[i].cnt);
int now=ll-;
for(int i=;i<=l1;i++)
t[++now]=q1[i];
for(int i=;i<=l2;i++)
t[++now]=q2[i];
}
void div(int ll,int rr,int dl,int dr)
{
if(dl==dr){
for(int i=ll;i<=rr;i++)
if(t[i].ki==)ans[t[i].id]=dl;
return ;
}
int mid=(dl+dr)>>;
count(ll,rr,dl,mid);
int p=l1;
if(p)
div(ll,ll+p-,dl,mid);
if(p<=rr-ll)
div(ll+p,rr,mid+,dr);
}
int main()
{
n=gi();
for(int i=;i<=n;i++)
val[i]=gi();
int x,y;
for(int i=;i<n;i++){
x=gi();y=gi();
init(x,y);init(y,x);
}
dfs();
for(int i=;i<=n;i++){
a[dfn[i]]=val[i];
t[++tot]=(node){,dfn[i],val[i],,,};
}
m=gi();
int flag,z,qnum=;
for(int i=;i<=m;i++)
{
flag=gi();
if(flag==){
x=gi();y=gi();
t[++tot]=(node){,dfn[x],last[x],y,,++qnum};
}
else
if(flag==){
x=gi();y=gi();z=gi();
t[++tot]=(node){,dfn[x],last[x],y,-,++qnum};
t[++tot]=(node){,dfn[x],last[x],z+,,qnum};
}
else{
x=gi();y=gi();
t[++tot]=(node){,dfn[x],a[dfn[x]],,-,};
t[++tot]=(node){,dfn[x],y,,,};
a[dfn[x]]=y;
}
}
div(,tot,,);
for(int i=;i<=qnum;i++)printf("%d\n",ans[i]);
return ;
}