简单的 RMQ； 先预处理得到 所有 节点的 公共祖先 和 dfs 得到所有节点的父亲节点； 然后 询问时，从自己出发向上找父亲， 然后 得到所有的节点；排序一下
不知道 这题这样也能过；为什么不会超时啊？？？？？？？？？？？；
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<vector>
using namespace std;
const int maxn = ;
struct date{
int v,next;
}edge[maxn<<]; int total,head[maxn];
int N,Q,node[maxn],fath[maxn];
void add_edge( int u,int v ){
edge[total].v = v;
edge[total].next = head[u];
head[u] = total++;
}
bool vis[maxn]; int dep[maxn<<],sta[maxn<<],tab[maxn<<],dp[maxn<<][],num;
void dfs1( int son,int fa ){
vis[son] = true; fath[son] = fa;
for( int i = head[son]; i != -; i = edge[i].next ){
int v = edge[i].v;
if( !vis[v] )dfs1( v,son );
}
}
void LCA( int son,int deep ){
dep[num] = deep; sta[son] = num; tab[num] = son; num++; vis[son] = true;
for( int i = head[son]; i != -; i = edge[i].next ){
int v = edge[i].v;
if( !vis[v] ){ LCA( v,deep+ ); dep[num] = deep; tab[num] = son; num++; }
}
}
int work( int n1,int n2 ){
if( dep[n1] < dep[n2] )return n1;
return n2;
}
void RMQ( ){
for( int i = ; i <= num; i++ )dp[i][] = i;
for( int i = ; (<<i) <= num; i++ ){
for( int j = ; j - + (<<i) <= num; j++ )
dp[j][i] = work( dp[j][i-], dp[j+(<<(i-))][i-] );
}
}
int query( int L,int R ){
int k = ;
while( (<<(k+)) <= R-L+ )k++;
return tab[work( dp[L][k],dp[R-(<<k)+][k] )];
}
vector<int>vv;
bool cmp( int a,int b ){
return a > b;
}
void DO( int u,int v,int fa,int k ){
vv.clear();
while( u != fa ){
vv.push_back( node[u] );
u = fath[u];
}
while( v != fa ){
vv.push_back( node[v] );
v = fath[v];
}
vv.push_back( node[fa] ); sort( vv.begin(),vv.end(),cmp );
//for( int i = 0; i < vv.size(); i++ )cout<<vv[i]<<endl;
if( vv.size() < k )puts("invalid request!");
else printf("%d\n",vv[k-]);
}
int main(){
while( scanf("%d%d",&N,&Q) != EOF ){
memset( head,-,sizeof(head) ); total = ;
for( int i = ; i <= N; i++ )fath[i] = i;
for( int i = ; i <= N; i++ )scanf("%d",&node[i]);
for( int i = ; i < N; i++ )
{
int u,v; scanf("%d%d",&u,&v);
add_edge( u,v );
add_edge( v,u );
}
memset( vis,,sizeof(vis) );
dfs1( ,- ); fath[] = ;
memset( vis,,sizeof(vis) );num = ;
LCA( , );
//for( int i = 1; i < num; i++ )
//cout<<i<<" "<<dep[i]<<" "<<tab[i]<<endl;
num--; RMQ( );
while( Q-- ){
int k,u,v; scanf("%d%d%d",&k,&u,&v);
if( k == ){ node[u] = v; continue; }
//cout<<node[4]<<endl;
if( sta[u] > sta[v] )swap( u,v );
//cout<<query( sta[u],sta[v] )<<endl;
DO( u,v,query( sta[u],sta[v] ),k );
}
}
return ;
}
/* 7 100
5 1 4 2 4 3 6
1 2
1 3
1 4
2 5
3 6
4 7 */