题意：n个点，n-1条边构成无向树，每个节点有权，Q次询问，每次或问从a->b的最短路中,权第k大的值，/或者更新节点a的权，
思路：在线LCA，先dfs生成树0，标记出层数和fa[](每个节点的父亲节点)。在对每次询问，走一遍一次公共祖先路上
的权，保持，快排。n*logn*q
#include<iostream> //187MS
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
int n,q;
int w[90000];
vector<vector<int> >e(160100);
int lev[80010];int vis[80010];
int fa[80010];
void dfs_getlev(int u) //dfs
{
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(!vis[v])
{
vis[v]=1;
lev[v]=lev[u]+1;
fa[v]=u;
dfs_getlev(v);
}
}
}
bool my(int a,int b)
{
return a>b;
}
int find_lca(int k,int a,int b) //在线lca，按层次向上走。
{
vector<int> ans;
if(lev[a]>lev[b])
{
int temp=a;a=b;b=temp;
}
while(lev[b]>lev[a])
{
ans.push_back(w[b]);
b=fa[b];
}
while(a!=b)
{
ans.push_back(w[b]);
ans.push_back(w[a]);
a=fa[a];
b=fa[b];
}
ans.push_back(w[b]);
if(k>ans.size()) return -1;
sort(ans.begin(),ans.end(),my);
return ans[k-1];
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
int ta,tb;
for(int i=0;i<n-1;i++)
{
scanf("%d%d",&ta,&tb);
e[ta].push_back(tb);
e[tb].push_back(ta);
}
vis[1]=lev[1]=1;
dfs_getlev(1);
int k,a,b;
while(q--)
{
scanf("%d%d%d",&k,&a,&b);
if(k>0)
{
int anss =find_lca(k,a,b);
if(anss!=-1)
printf("%d\n",anss);
else
printf("invalid request!\n");
}
else
{
w[a]=b;
}
}
return 0;
}