题意：有 n 点的一颗树，每个节点有格子的权值，现在有两种操作，修改一个点的权值，或者求两点之间的路径上的第 k 大的权值。
其实看到这个题，就在 YY 各种做法，询问后得到貌似可能是关于主席树、树链剖分等高端数据结构做的，但事实上，大概是出题人也并不想出难题，只是为了练练手所以……直接把每个问题路径上的点权保存在数组中 sort 一下就行了。然后树上路径就果断是LCA了，不过这里LCA也就不用倍增了，直接一步一步向上爬然后顺便加数组就行了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; const int maxn=8e4+;
const int maxm=maxn*; int fa[maxn],dep[maxn];
int head[maxn],point[maxm],nxt[maxm],size;
int n,num[maxn],que[maxn],cnt; void init(){
size=;
memset(head,-,sizeof(head));
} void add(int a,int b){
point[size]=b;
nxt[size]=head[a];
head[a]=size++;
point[size]=a;
nxt[size]=head[b];
head[b]=size++;
} void Dfs(int s,int pre){
fa[s]=pre;
dep[s]=dep[pre]+;
for(int i=head[s];~i;i=nxt[i]){
int j=point[i];
if(j==pre)continue;
Dfs(j,s);
}
} void Pre(){
dep[]=;
Dfs(,-);
} void Lca(int u,int v){
cnt=;
if(dep[u]>dep[v])swap(u,v);
while(dep[u]<dep[v]){
que[++cnt]=num[v];
v=fa[v];
}
while(u!=v){
que[++cnt]=num[u];
u=fa[u];
que[++cnt]=num[v];
v=fa[v];
}
que[++cnt]=num[u];
} int main(){
int m;
scanf("%d%d",&n,&m);
init();
for(int i=;i<=n;++i)scanf("%d",&num[i]);
for(int i=;i<n;++i){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
Pre();
while(m--){
int f,a,b;
scanf("%d%d%d",&f,&a,&b);
if(f){
Lca(a,b);
if(cnt<f)printf("invalid request!\n");
else{
sort(que+,que+cnt+);
printf("%d\n",que[cnt-f+]);
}
}
else num[a]=b;
}
}