题意：
n个点 m个询问
下面n个数字表示点权值
n-1行给定一棵树
m个询问 k u v
k为0时把u点权值改为v
或者问 u-v的路径上 第k大的数
思路：
LCA转RMQ求出 LCA(u,v) ;
登山坡式找到路径上所有点并记录其权值
排序输出k大的数
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<math.h>
#define N 80010
using namespace std;
inline int Max(int a,int b){return a>b?a:b;} struct node{
int from, to, nex;
}edge[N<<1];
int head[N], edgenum;
void addedge(int u, int v){
node E = {u, v, head[u]};
edge[ edgenum ] = E;
head[u] = edgenum ++;
}
int val[N], Stack[N]; int time;
int deep[N<<1], index[N<<1], first[N], pre[N];
void DFS(int u, int dep){
deep[time] = u;
index[time] =u;
time++;
for(int i = head[u]; i !=-1; i = edge[i].nex)
{
int v = edge[i].to;
if(first[v] == 0)
{
first[v] = time;
pre[v] = u;
DFS(v, dep+1);
deep[time] = u;
index[time]= u;
time++;
}
}
}
int dp[N<<1][25];
void RMQ_init(int n){
for(int i = 1; i <= n; i++)
dp[i][0] = i;
for(int j = 1; (1<<j)<=n;j++)
{
int k = 1<<(j-1);
for(int i = 1; i+k<n; i++)
{
if(deep[ dp[i][j-1] ] <= deep[ dp[i+k][j-1] ])
dp[i][j] = dp[i][j-1];
else
dp[i][j] = dp[i+k][j-1];
}
}
}
int RMQ(int a,int b){
int dis = Max(a-b,b-a) +1;
int k = log(double(dis))/ log(2.0);
if(deep[dp[a][k]]<= deep[dp[b - (1<<k) +1][k]])
return dp[a][k];
else
return dp[b-(1<<k)+1][k];
}
int LCA(int u, int v){
int fu = first[u], fv = first[v];
return fu<=fv? index[ RMQ(fu,fv)] : index[ RMQ(fv,fu)];
} int main()
{
int n, m, i, j, k, que, u, v;
int root = 1;
while(~scanf("%d%d",&n,&que))
{
memset(head, -1, sizeof(head)); edgenum = 0;
memset(first, 0, sizeof(first)); for(i=1;i<=n;i++)scanf("%d",&val[i]);
for(i=1;i<n;i++)
{
scanf("%d %d",&u,&v);
addedge(u, v); addedge(v, u);
}
first[root] = 1;
time = 1;
DFS(root, 0);
RMQ_init(time-1);
while(que--){
scanf("%d %d %d",&k,&u,&v);
if(k==0)
{val[u] = v; continue;}
if(u==v){
if(k==1)printf("%d\n",val[u]);
else printf("invalid request!\n");continue;
}
int c = LCA(u, v);
int top = 0;
Stack[top++] = val[c];
while(u!=c)
{
Stack[top++] = val[u];
u = pre[u];
}
while(v!=c)
{
Stack[top++] = val[v];
v = pre[v];
}
if(top<k)
{printf("invalid request!\n");continue;}
sort(Stack, Stack+top);
printf("%d\n",Stack[top - k]);
}
}
return 0;
}
8 99
5 2 3 4 5 6 7 8
1 3
1 2
3 4
3 5
5 6
5 7
7 8
1 2 8
2 2 8
3 2 8
4 2 8
5 2 8
6 2 8
7 2 8
1 4 8
4 2 3
5 3 8
2 3 8
0 3 8
2 3 8
3 3 8
2 4 5
1 4 1
2 4 1
3 4 1 ans:
8
7
5
5
3
2
in...
8
in...
in...
7
8
7
5
8
5
4 1 1
5
1 1 1 ans:
5 2 2
2 1
1 2
2 2 1
1 1 2 ans:
1
2