题目链接：BZOJ1146
【分析】这题最容易想到的就是二分答案+树链剖分+线段树套BST，但是复杂度有q*logn^4，而且代码量极大，本人太懒不想写了，学习了一种神一样的解法；而且复杂度才q*logn^2；
首先BZOJ2588可以知道，对于静态树上第K大，可以在每个点建一棵到根的前缀可持久化线段树，则查询任意两点间(x,y)的第k大可以在主席树T=a[x]+a[y]-2*[LCA(x,y)];由于是点所以变成T = a[x]+a[y]-a[LAC(x,y)]-a[fa[LCA(x,y)]];这个查询可以在主席树带入这四个点实现O(logn)的查询。然后这题是可修改的，如果直接套上树状数组没法在树上维护前缀和，怎么办？可以用DFS序呀！对于每一个点，在其入栈的时候加上，在出栈的时候减去。那么如果查询一个点入栈位置的前缀和，就是它到根的路径的信息。这样就转变成了区间可修改第k大+静态树上K大，查询时带入树状数组表示的值树按照这个公式T=a[x]+a[y]-2*[LCA(x,y)]计算即可。查询复杂度O(logn^2),可以配合静态n*logn预处理加上另外维护修改可以把空间复杂度降到n*logn+n*logn^2
【AC CODE】5188ms
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 80000+10, MAXQ = 80000+10, MAXM = 80*MAXN;
struct IN{
int k,a,b;
}in[MAXQ];
int a[MAXN],n,num[MAXN+MAXQ],cnt,sot[MAXN+MAXQ],head[MAXN],e,nxt[MAXN<<1],to[MAXN<<1];
int sum[MAXM], lc[MAXM],rc[MAXM],tol;
int rt[MAXN<<2];
inline void add_edge(int u, int v)
{
nxt[e] = head[u], to[e] = v;
head[u] = e++;
}
inline int mhash(int v){return lower_bound(sot+1,sot+1+cnt,v)-sot;}
int fa[MAXN], ft[MAXN], d[MAXN<<1],id[MAXN<<1],all;
int df[MAXN<<1],st[MAXN],ed[MAXN],dcnt;
bool ised[MAXN<<1];
void dfs(int u, int dep)
{
ft[u] = all, d[all] = dep, id[all++] = u;
df[++dcnt] = a[u];st[u] = dcnt;ised[dcnt] = 0;
for(int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if(v == fa[u]) continue;
fa[v] = u;
dfs(v,dep+1);
d[all] = dep, id[all++] = u;
}
df[++dcnt] = a[u];ed[u] = dcnt;ised[dcnt] = 1;
}
int dp[MAXN<<1][21], dp_num[MAXN<<1][21];//dp_num记录dp对应的点的编号
void st_init()
{
rep(i,0,all) dp[i][0] = d[i], dp_num[i][0] = id[i];
for(int j = 1; (1<<j) <= all; j++)
{
for(int i = 0; i+(1<<j)-1 < all; i++)
{
if(dp[i][j-1] < dp[i+(1<<(j-1))][j-1])
{
dp[i][j] = dp[i][j-1];
dp_num[i][j] = dp_num[i][j-1];
}
else
{
dp[i][j] = dp[i+(1<<(j-1))][j-1];
dp_num[i][j] = dp_num[i+(1<<(j-1))][j-1];
}
}
}
}
int st_query(int x, int y)
{
if(x > y) swap(x,y);
int k = 0;
while((1<<(k+1)) <= y-x+1) k++;
if(dp[x][k] <= dp[y-(1<<k)+1][k]) return dp_num[x][k];
return dp_num[y-(1<<k)+1][k];
}
int lca_query(int x, int y){ return st_query(ft[x],ft[y]);}//x,y的LCA, O(1)
void bulid(int &u, int x, int y, int p, int v)
{
sum[++tol] = sum[u]+v,lc[tol] = lc[u],rc[tol] = rc[u];
u = tol;
if(x == y) return;
int m = (x+y)>>1;
if(p <= m) bulid(lc[u],x,m,p,v);
else bulid(rc[u],m+1,y,p,v);
}
void init()
{
all = tol = 0;
clc(rt,0);
dfs(1,0);
st_init();
rt[dcnt+1] = rt[0];
bulid(rt[dcnt+1],1,cnt,mhash(df[1]),1);
repe(i,2,dcnt)
{
rt[i+dcnt] = rt[i-1+dcnt];
int v = 1;
if(ised[i]) v = -1;
bulid(rt[i+dcnt],1,cnt,mhash(df[i]),v);
}
}
void t_update(int &u, int x, int y, int p, int v)
{
if(!u) {lc[++tol] = lc[u],rc[tol] = rc[u], sum[tol] = sum[u];u = tol;}
sum[u] += v;
if(x == y) return;
int m = (x+y)>>1;
if(p <= m) t_update(lc[u],x,m,p,v);
else t_update(rc[u],m+1,y,p,v);
}
inline int lowbit(int x){return x&-x;}
void add(int x, int v)
{
int p = mhash(df[x]);
while(x <= dcnt)
{
t_update(rt[x],1,cnt,p,v);
x += lowbit(x);
}
}
void update(int x, int v)
{
add(st[x],-1);//第一次出现点删掉原来加上新的
df[st[x]] = v;
add(st[x],1);
add(ed[x],1);//最后一次出现点相反
df[ed[x]] = v;
add(ed[x],-1);
}
int tx[100],ty[100],len[2];
int query(int x, int y, int k)
{
if(x == y) return x;
int m = (x+y)>>1, tmp = 0;
rep(i,0,len[1]) tmp += sum[rc[ty[i]]];
rep(i,0,len[0]) tmp -= sum[rc[tx[i]]];
if(tmp >= k)
{
rep(i,0,len[1]) ty[i] = rc[ty[i]];
rep(i,0,len[0]) tx[i] = rc[tx[i]];
return query(m+1,y,k);
}
rep(i,0,len[1]) ty[i] = lc[ty[i]];
rep(i,0,len[0]) tx[i] = lc[tx[i]];
return query(x,m,k-tmp);
}
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
#endif
int q;
scanf("%d %d",&n, &q);
int cc = 0;
repe(i,1,n) scanf("%d", &a[i]), num[++cc] = a[i];
e = 0;
clc(head,-1);
rep(i,1,n)
{
int u,v;
scanf("%d %d", &u, &v);
add_edge(u,v);
add_edge(v,u);
}
rep(i,0,q)
{
scanf("%d %d %d", &in[i].k, &in[i].a, &in[i].b);
if(!in[i].k) num[++cc] = in[i].b;
}
sort(num+1,num+1+cc);
sot[cnt=1] = num[1];
repe(i,2,cc) if(num[i] != num[i-1]) sot[++cnt] = num[i];
init();
rep(i,0,q)
{
if(in[i].k)
{
len[0]=len[1]=0;
int lca = lca_query(in[i].a,in[i].b);
int ta = st[in[i].a], tb = st[in[i].b],tlca = st[lca],tflca = st[fa[lca]];
ty[len[1]++] = rt[ta+dcnt],ty[len[1]++] = rt[tb+dcnt];//静态初始值
for(int j = ta; j > 0; j -= lowbit(j)) ty[len[1]++] = rt[j];
for(int j = tb; j > 0; j -= lowbit(j)) ty[len[1]++] = rt[j];
tx[len[0]++] = rt[tlca+dcnt],tx[len[0]++] = rt[tflca?tflca+dcnt:0];
for(int j = tlca; j > 0; j -= lowbit(j)) tx[len[0]++] = rt[j];
for(int j = tflca; j > 0; j -= lowbit(j)) tx[len[0]++] = rt[j];
int tmp = 0;
rep(j,0,len[1]) tmp += sum[ty[j]];
rep(j,0,len[0]) tmp -= sum[tx[j]];
if(tmp < in[i].k) puts("invalid request!");
else printf("%d\n", sot[query(1,cnt,in[i].k)]);
}
else
update(in[i].a,in[i].b);
}
return 0;
}
