很久之前写过 count on the tree。
然后一直不懂树状数组是怎么套上这个主席树的。
看了两小时发现它套的就是个权值线段树，
看不出来可持久化在哪里。
因为动态开点所以空间nlog2n。
树状数组维护dfs序，每个节点挂个线段树。
为了省空间拿原树建了个主席树。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 80005
using namespace std;
int n,q;
int t[N];
int head[N],ver[N*],nxt[N*],tot;
int li[N*],now[N*],cnt;
void add(int a,int b)
{
tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;
}
struct node
{
int k,a,b;
}qq[N];
int zz,st[N],ed[N];
int dep[N];
int fa[N][];
void lca()
{
for(int i=;i<=;i++)
for(int j=;j<=n;j++)
fa[j][i]=fa[fa[j][i-]][i-];
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=;i>=;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=;i>=;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];y=fa[y][i];
}
}
return fa[x][];
}
void dfs(int x,int f)
{
st[x]=++zz;
for(int i=head[x];i;i=nxt[i])
{
if(ver[i]==f)continue;
fa[ver[i]][]=x;
dep[ver[i]]=dep[x]+;
dfs(ver[i],x);
}
ed[x]=zz;
}
int root[N],rot[N];
struct Node
{
int l,r,sum;
}a[N*];
int num; void inrt(int x,int y,int l,int r,int pos)
{
if(l==r)
{
a[x].sum=a[y].sum+;
return ;
}
int mid=(l+r)>>;
if(pos<=mid)
{
if(!a[x].l)a[x].l=++num;
a[x].r=a[y].r;
inrt(a[x].l,a[y].l,l,mid,pos);
}
else
{
if(!a[x].r)a[x].r=++num;
a[x].l=a[y].l;
inrt(a[x].r,a[y].r,mid+,r,pos);
}
a[x].sum=a[a[x].l].sum+a[a[x].r].sum;
}
void build()
{
for(int i=;i<=n;i++)
{
if(!rot[i])rot[i]=++num;
inrt(rot[i],rot[fa[i][]],,cnt,now[i]);
}
}
void insert(int x,int l,int r,int pos,int z)
{
if(l==r)
{
a[x].sum+=z;return ;
}
int mid=(l+r)>>;
if(pos<=mid)
{
if(!a[x].l)a[x].l=++num;
insert(a[x].l,l,mid,pos,z);
}
else
{
if(!a[x].r)a[x].r=++num;
insert(a[x].r,mid+,r,pos,z);
}
a[x].sum=a[a[x].l].sum+a[a[x].r].sum;
}
void ad(int x,int z,int la)
{
for(int i=x;i<=n;i+=(i&(-i)))
{
if(!root[i])root[i]=++num;
insert(root[i],,cnt,z,la);
}
return ;
}
int no[N][];
int t1,t2,t3,t4;
int qur(int x,int y)
{
int as=;
for(int i=x;i;i-=(i&(-i)))
{
as+=a[a[no[i][y]].l].sum;
}
return as;
}
int qur(int l,int r,int kk,int r1,int r2,int r3,int r4)
{
if(l==r)
{
return l;
}
int mid=(l+r)>>;
int xx=a[a[r3].l].sum+a[a[r4].l].sum-a[a[r1].l].sum-a[a[r2].l].sum;
xx+=qur(st[t1],);xx+=qur(st[t2],);
xx-=qur(st[t3],);xx-=qur(st[t4],);
if(xx>=kk)
{
for(int i=st[t1];i;i-=(i&(-i)))no[i][]=a[no[i][]].l;
for(int i=st[t2];i;i-=(i&(-i)))no[i][]=a[no[i][]].l;
for(int i=st[t3];i;i-=(i&(-i)))no[i][]=a[no[i][]].l;
for(int i=st[t4];i;i-=(i&(-i)))no[i][]=a[no[i][]].l;
return qur(l,mid,kk,a[r1].l,a[r2].l,a[r3].l,a[r4].l);
}
else
{
for(int i=st[t1];i;i-=(i&(-i)))no[i][]=a[no[i][]].r;
for(int i=st[t2];i;i-=(i&(-i)))no[i][]=a[no[i][]].r;
for(int i=st[t3];i;i-=(i&(-i)))no[i][]=a[no[i][]].r;
for(int i=st[t4];i;i-=(i&(-i)))no[i][]=a[no[i][]].r;
return qur(mid+,r,kk-xx,a[r1].r,a[r2].r,a[r3].r,a[r4].r);
}
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)scanf("%d",&t[i]),li[++cnt]=t[i];
for(int i=;i<n;i++)
{
scanf("%d%d",&t1,&t2);
add(t1,t2);add(t2,t1);
}
for(int i=;i<=q;i++)
{
scanf("%d%d%d",&qq[i].k,&qq[i].a,&qq[i].b);
if(!qq[i].k)li[++cnt]=qq[i].b;
}
sort(li+,li+cnt+);
cnt=unique(li+,li+cnt+)-li-;
for(int i=;i<=n;i++)now[i]=lower_bound(li+,li+cnt+,t[i])-li;
dep[]=;dfs(,-);
lca();
build();
for(int i=;i<=q;i++)
{
if(!qq[i].k)
{
ad(st[qq[i].a],now[qq[i].a],-);
if(ed[qq[i].a]!=zz)ad(ed[qq[i].a]+,now[qq[i].a],);
now[qq[i].a]=lower_bound(li+,li+cnt+,qq[i].b)-li;
ad(st[qq[i].a],now[qq[i].a],);
if(ed[qq[i].a]!=zz)ad(ed[qq[i].a]+,now[qq[i].a],-);
}
else
{
int tmp=lca(qq[i].a,qq[i].b);
int yy=dep[qq[i].a]+dep[qq[i].b]-dep[tmp]*+;
if(yy<qq[i].k)
{
puts("invalid request!");
continue;
}
else
{
yy=yy-qq[i].k+;
for(int j=st[qq[i].a];j;j-=(j&(-j)))no[j][]=root[j];
for(int j=st[qq[i].b];j;j-=(j&(-j)))no[j][]=root[j];
for(int j=st[tmp];j;j-=(j&(-j)))no[j][]=root[j];
for(int j=st[fa[tmp][]];j;j-=(j&(-j)))no[j][]=root[j];
t1=qq[i].a;t2=qq[i].b;t3=tmp;t4=fa[tmp][];
int tp=qur(,cnt,yy,rot[tmp],rot[fa[tmp][]],rot[qq[i].a],rot[qq[i].b]);
printf("%d\n",li[tp]);
}
}
}
return ;
}