题意：#
一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。
思路：#
暴力即可orz(数据是真的水啊。
求路径上的点的时候需要用到LCA
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年07月31日 星期一 01时12分54秒
4File Name :3078.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=8E4+7;
35int n,q;
36int val[N];
37vector < pi > edge[N];
38int in[N];
39int E[2*N],R[2*N],dis[N],depth[2*N];
40int p;
41int fa[N];
42int dp[2*N][20];
43void dfs( int u,int dep,int d,int pre)
44{
45
46 // cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl;
47 fa[u] = pre;
48 p++;
49 E[p] = u;
50 depth[p] = dep;
51 R[u] = p ;
52 dis[u] = d;
53
54
55 int siz = edge[u].size();
56 for ( int i = 0 ; i < siz ; i++)
57 {
58 int v = edge[u][i].fst;
59 if (v==pre) continue;
60 dfs(v,dep+1,d+edge[u][i].sec,u);
61
62 p++;
63 E[p] = u;
64 depth[p] = dep;
65 }
66}
67
68
69
70int _min( int l,int r)
71{
72 if (depth[l]<depth[r]) return l;
73 return r;
74}
75void rmq_init()
76{
77 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i;
78
79 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++)
80 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++)
81 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
82}
83
84int rmq_min( int l,int r)
85{
86 if (l>r) swap(l,r);
87 int k = 0 ;
88 while (1<<(k+1)<=r-l+1) k++;
89 return _min(dp[l][k],dp[r-(1<<k)+1][k]);
90}
91int D(int u,int v) //计算u,v点的距离
92{
93 int LCA = E[rmq_min(R[u],R[v])];
94 int res = dis[u] + dis[v] - 2*dis[LCA];
95 return res;
96}
97void get_path(vector<int> &v,int s,int t)
98{
99 while (s!=t)
100 {
101 v.PB(val[s]);
102 s = fa[s];
103 }
104}
105bool cmp(int a ,int b){return a>b;}
106void solve(int k,int u,int v)
107{
108 int LCA = E[rmq_min(R[u],R[v])];
109 vector<int>path;
110 get_path(path,u,LCA);
111 get_path(path,v,LCA);
112 path.PB(val[LCA]);
113 sort(path.begin(),path.end(),cmp);
114 int siz = path.size();
115 // for ( int i = 0 ; i < siz ; i++) printf("%d ",path[i]);
116 // printf("\n");
117 if (k>siz)
118 {
119 puts("invalid request!");
120 return;
121 }
122 printf("%d\n",path[k-1]);
123
124}
125int main()
126{
127 #ifndef ONLINE_JUDGE
128 freopen("./in.txt","r",stdin);
129 #endif
130 while (~scanf("%d%d",&n,&q))
131 {
132 ms(val,0);
133 for ( int i = 1 ;i <= n ; i++) scanf("%d",&val[i]);
134 for ( int i = 1 ; i <= n-1 ; i++)
135 {
136 int u,v;
137 scanf("%d%d",&u,&v);
138 edge[u].PB(MP(v,1));
139 edge[v].PB(MP(u,1));
140 }
141 p = 0 ;
142 dfs(1,0,0,-1);
143 rmq_init();
144 while (q--)
145 {
146 int k,u,v;
147 scanf("%d%d%d",&k,&u,&v);
148 if (k==0)
149 {
150 val[u] = v;
151 }
152 else
153 {
154 solve(k,u,v);
155 }
156 }
157 }
158
159
160 #ifndef ONLINE_JUDGE
161 fclose(stdin);
162 #endif
163 return 0;
164}