放一下朴素的狂T代码：
```cpp
#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<cstring>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=160005;
struct edge
{
int to,nxt;
}e[N]; int n,m,head[N],a[N],rst[N],cnt,tot,fir[N],lst[N],s[N],blk[N];
struct ques
{
int x,y,ex,t,id,rk;
inline friend bool operator < (const ques& A,const ques& B)
{
if (blk[A.x]<blk[B.x]) return 1; if (blk[A.x]>blk[B.x]) return 0;
if (blk[A.y]<blk[B.y]) return 1; if (blk[A.y]>blk[B.y]) return 0;
return A.t<B.t;
}
}q[N]; bool tag[N]; int cnt_q,L,R,nt,ans[N];
struct event
{
int x,y;
}p[N]; int pre[N],cnt_p,size,opt,x,y;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))
char Fin[S],Fout[S],*A,*B; int pt[15],Ftop;
public:
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x)
{
if (!x) return (void)(pc('0'),pc('\n')); if (x<0) pc('-'),x=-x; RI ptop=0;
while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc('\n');
}
inline void ps(const char* s)
{
int len=strlen(s); for (RI i=0;i<len;++i) pc(s[i]);
}
inline void Fend(void)
{
fwrite(Fout,1,Ftop,stdout);
}
#undef tc
#undef pc
}F;
inline void swap(int& x,int& y)
{
int t=x; x=y; y=t;
}
inline int find(CI x)
{
return lower_bound(rst+1,rst+tot+1,x)-rst;
}
inline void addedge(CI x,CI y)
{
e[++cnt]=(edge){y,head[x]}; head[x]=cnt;
e[++cnt]=(edge){x,head[y]}; head[y]=cnt;
}
class Euler_Order_Solver
{
private:
static const int P=18;
int dep[N],anc[N][P],idx;
inline void reset(CI now)
{
for (RI i=0;i<P-1;++i) if (anc[now][i])
anc[now][i+1]=anc[anc[now][i]][i]; else break;
}
public:
#define to e[i].to
inline void DFS(CI now,CI fa)
{
dep[now]=dep[fa]+1; s[fir[now]=++idx]=now; reset(now);
for (RI i=head[now];i;i=e[i].nxt) if (to!=fa)
anc[to][0]=now,DFS(to,now); s[lst[now]=++idx]=now;
}
#undef to
inline int LCA(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y); RI i; for (i=P-1;~i;--i)
if (dep[anc[x][i]]>=dep[y]) x=anc[x][i]; if (x==y) return x;
for (i=P-1;~i;--i) if (anc[x][i]!=anc[y][i])
x=anc[x][i],y=anc[y][i]; return anc[x][0];
}
}T;
class Brute_Blocks
{
private:
static const int BLO=405;
int blk[N],bkt[N],sum[BLO],size;
inline int min(CI a,CI b)
{
return a<b?a:b;
}
inline int get(CI pos,int rk)
{
int lw=(pos-1)*size+1,up=min(pos*size,tot);
for (RI i=up;i>=lw;--i) if (rk<=bkt[i]) return i; else rk-=bkt[i];
}
public:
inline void init(void)
{
size=sqrt(tot); for (RI i=1;i<=tot;++i) blk[i]=(i-1)/size+1;
}
inline void add(CI x)
{
++bkt[x]; ++sum[blk[x]];
}
inline void del(CI x)
{
--bkt[x]; --sum[blk[x]];
}
inline int query(int rk)
{
RI i; for (i=blk[tot];i;--i) if (rk<=sum[i]) return get(i,rk);
else rk-=sum[i]; return -1;
}
}B;
inline void travel(CI nt)
{
if (tag[p[nt].x]) B.del(a[p[nt].x]),B.add(p[nt].y);
pre[nt]=a[p[nt].x]; a[p[nt].x]=p[nt].y;
}
inline void retime(CI nt)
{
if (tag[p[nt].x]) B.del(a[p[nt].x]),B.add(pre[nt]);
a[p[nt].x]=pre[nt];
}
inline bool expand(CI x)
{
if (tag[x]) B.del(a[x]); else B.add(a[x]); tag[x]^=1;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (F.read(n),F.read(m),i=1;i<=n;++i) F.read(a[i]),rst[i]=a[i];
for (i=1;i<n;++i) F.read(x),F.read(y),addedge(x,y); tot=n;
for (size=pow(n,2.0/3.0),i=1;i<=n;++i) blk[i]=(i-1)/size+1;
for (T.DFS(1,0),i=1;i<=m;++i)
{
F.read(opt); F.read(x); F.read(y);
if (!opt) ++cnt_p,p[cnt_p].x=x,rst[++tot]=p[cnt_p].y=y; else
{
q[++cnt_q].t=cnt_p; q[cnt_q].rk=opt; q[cnt_q].id=cnt_q;
if (fir[x]>fir[y]) swap(x,y); int fa=T.LCA(x,y);
q[cnt_q].y=fir[y]; if (x==fa) q[cnt_q].x=fir[x];
else q[cnt_q].x=lst[x],q[cnt_q].ex=fa;
}
}
sort(rst+1,rst+tot+1); tot=unique(rst+1,rst+tot+1)-rst-1;
for (i=1;i<=n;++i) a[i]=find(a[i]); for (i=1;i<=cnt_p;++i) p[i].y=find(p[i].y);
//for (RI i=1;i<=n;++i) printf("%d ",fir[i]); putchar('\n');
//for (RI i=1;i<=n;++i) printf("%d ",lst[i]); putchar('\n');
//for (RI i=1;i<=n<<1;++i) printf("%d ",s[i]); putchar('\n');
for (B.init(),sort(q+1,q+cnt_q+1),L=i=1;i<=cnt_q;++i)
{
while (nt<q[i].t) travel(++nt); while (nt>q[i].t) retime(nt--);
while (L>q[i].x) expand(s[--L]); while (R<q[i].y) expand(s[++R]);
while (L<q[i].x) expand(s[L++]); while (R>q[i].y) expand(s[R--]);
if (q[i].ex) expand(q[i].ex); ans[q[i].id]=B.query(q[i].rk); if (q[i].ex) expand(q[i].ex);
}
for (i=1;i<=cnt_q;++i) if (~ans[i]) F.write(rst[ans[i]]); else F.ps("invalid request!\n");
return F.Fend(),0;
}
```
by hl666 @ 2019-03-18 17:32:16
STO $\color{black}\texttt{h}\color{red}\texttt{l666}$ ORZ
by xryjr233 @ 2019-03-18 17:32:46
好了是我真的ZZ，树上莫队的下标范围是$2n$的
改了下就不开O2过了~~一个点200ms，，，~~~
此贴终结（我是真的菜）
by hl666 @ 2019-03-18 17:37:00
$\color{black}\texttt{h}\color{red}\texttt{l666}\ \ \ $fake
by da32s1da @ 2019-03-18 17:41:16
@[da32s1da](/space/show?uid=50092) 您真是又强又Fake
by hl666 @ 2019-03-18 17:43:29
@[hl666](/space/show?uid=41698) 为什么您的根号比我的两个$log$快那么多啊啊啊啊啊啊啊啊
by star_city @ 2019-03-18 17:44:34
@[star_city](/space/show?uid=47421) 这题数据本来就玄学吧。。。
不是说$4$个$\log$都能过么，莫队一般都跑不满的吧（加了奇偶数判断常数很小）
by hl666 @ 2019-03-18 17:47:26
STO hl666 Orz
by Cptraser @ 2019-03-18 18:10:12
STO hl666 Orz
by TheLostWeak @ 2019-04-10 18:33:56