其实也没啥好说的
用树状数组可以O(logn)的查询
套一层整体二分就可以做到O(nlngn)
最后用树链剖分让序列上树
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
int x=,f=,ch=getchar();
while(ch<''||ch>''){if(ch=='-'){f=-;}ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,q;
int data[];
inline void add(int x,int i)
{
while(x<=n)
{
data[x]+=i;
x+=x&(-x);
}
}
inline int query(int x)
{
int res=;
while(x>=)
{
res+=data[x];
x-=x&(-x);
}
return res;
}
int h[],next[],to[],cnt;
inline void addedge(int x,int y)
{
next[cnt]=h[x];
to[cnt]=y;
h[x]=cnt;
cnt++;
}
int size[],hson[],dep[],f[];
inline void bfs(int x,int fa)
{
int i;
size[x]=;
for(i=h[x];i!=-;i=next[i])
{
if(to[i]==fa)
{
continue;
}
dep[to[i]]=dep[x]+;
f[to[i]]=x;
bfs(to[i],x);
size[x]+=size[to[i]];
if(size[to[i]]>size[hson[x]])
{
hson[x]=to[i];
}
}
}
int up[],first[],tim;
inline void spfa(int x,int tt)
{
tim++;
first[x]=tim;
up[x]=tt;
if(!hson[x])
{
return ;
}
spfa(hson[x],tt);
int i;
for(i=h[x];i!=-;i=next[i])
{
if(to[i]==f[x]||to[i]==hson[x])
{
continue;
}
spfa(to[i],to[i]);
}
}
inline int lca(int x,int y)
{
int res=;
while(up[x]!=up[y])
{
if(dep[up[x]]<dep[up[y]])
{
swap(x,y);
}
res+=query(first[x])-query(first[up[x]]-);
x=f[up[x]];
}
if(dep[x]>dep[y])
{
swap(x,y);
}
res+=query(first[y])-query(first[x]-);
return res;
}
struct stu
{
int op,l,r,id,x;
};
stu a[];
int ans[];
int m[];
stu q1[],q2[];
inline void erfen(int l,int r,int sl,int sr)
{
if(sl>sr)
{
return ;
}
if(l==r)
{
int i;
for(i=sl;i<=sr;i++)
{
if(a[i].op!=)
{
continue;
}
ans[a[i].id]=l;
}
return ;
}
int i,mid=(l+r)>>,k,cnt1=,cnt2=;
for(i=sl;i<=sr;i++)
{
if(a[i].op==)
{
if(a[i].x<=mid)
{
add(first[a[i].l],);
m[i]=;
}
else
{
m[i]=;
}
continue;
}
if(a[i].op==)
{
if(a[i].x<=mid)
{
add(first[a[i].l],-);
m[i]=;
}
else
{
m[i]=;
}
continue;
}
if(a[i].op==)
{
k=lca(a[i].l,a[i].r);
if(k<a[i].x)
{
a[i].x-=k;
m[i]=;
}
else
{
m[i]=;
}
}
}
for(i=sl;i<=sr;i++)
{
if(a[i].op==)
{
if(a[i].x<=mid)
{
add(first[a[i].l],-);
}
}
if(a[i].op==)
{
if(a[i].x<=mid)
{
add(first[a[i].l],);
}
}
if(m[i]==)
{
cnt1++;
q1[cnt1]=a[i];
}
else
{
cnt2++;
q2[cnt2]=a[i];
}
}
for(i=;i<=cnt1;i++)
{
a[sl+i-]=q1[i];
}
for(i=;i<=cnt2;i++)
{
a[sl+cnt1+i-]=q2[i];
}
erfen(l,mid,sl,sl+cnt1-);
erfen(mid+,r,sl+cnt1,sr);
}
int p[];
int main()
{
memset(h,-,sizeof(h));
memset(ans,0x3f,sizeof(ans));
n=read(),q=read();
int i,x,y,tail=,k,o;
for(i=;i<=n;i++)
{
x=read();
tail++;
a[tail].op=,a[tail].l=i,a[tail].x=x;
p[i]=x;
}
for(i=;i<n;i++)
{
x=read(),y=read();
addedge(x,y);
addedge(y,x);
}
dep[]=;
bfs(,-);
spfa(,);
for(i=;i<=n;i++)
{
add(first[i],);
}
for(i=;i<=q;i++)
{
k=read(),x=read(),y=read();
if(k==)
{
tail++;
a[tail].op=;a[tail].l=x,a[tail].x=p[x];
tail++;
a[tail].op=;a[tail].l=x;a[tail].x=y;
p[x]=y;
}
else
{
o=lca(x,y);
if(o<k)
{
ans[i]=-;
continue;
}
k=o-k+;
tail++;
a[tail].op=,a[tail].l=x,a[tail].r=y,a[tail].x=k;
a[tail].id=i;
}
}
memset(data,,sizeof(data));
erfen(,,,tail);
for(i=;i<=q;i++)
{
if(ans[i]==0x3f3f3f3f)
{
continue;
}
if(ans[i]==-)
{
puts("invalid request!");
}
else
{
printf("%d\n",ans[i]);
}
}
return ;
}