题意：n个点 m个询问，下面一行是n 个点的权值 再下面n-1行是双向的边
然后m个询问：k u v 若k==0，则把u点的权值改为v，否则回答u->v之间最短路经过点的权值中 第k大的值是多少
木有AC。。勿扔OJ
可以拿来学习RMQ
思路：跑个RMQ 求出LCA(u,v) 然后只要登山坡一遍就得到u->v的点，记下这些点的权值，再排个序就有第k大的数了
下面附几个测试案例和答案
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 80010 //最多有N个点
struct node{
int from,to,nex;
}edge[N];
int head[N],edgenum;
int a[N],pre[N],temp[N];//a[]是点的权值，temp是用来记录登山坡经过的点的权值
//pre记录点的前驱，用来登山坡
int E[N*2],R[N],D[N*2],en;//R[i]代表i点第一次搜到的位置 E[i]代表搜的第i次点的编号 D[i]代表搜的第i次点的深度
void add(int u,int v){//邻接表
edge[edgenum].from=u; edge[edgenum].to=v;
edge[edgenum].nex=head[u]; head[u]=edgenum++;
}
void DFS(int x,int deep){
E[en]=x;D[en]=deep;R[x]=en++;
for(int i=head[x];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(R[v]==-1)
{
pre[v]=x;
DFS(v,deep+1);
E[en]=x; D[en++]=deep;
}
}
}
int LCA(int u,int v){
int deep=N,t=u;
if(R[u]>R[v]){t=u;u=v;v=t;}
for(int i=R[u];i<=R[v];i++)
if(deep>D[i])
deep=D[i],t=i;
return E[t];
}
bool cmp(int a,int b){return a>b;}
void Findans(int u,int v,int k){
int lca=LCA(u,v),top=0;
temp[top++]=a[lca];
for(;u!=lca;u=pre[u])temp[top++]=a[u];//登山坡到LCA处
for(;v!=lca;v=pre[v])temp[top++]=a[v];
if(top<k)printf("invalid request!
");
else
{
sort(temp,temp+top,cmp);
printf("%d
",temp[k-1]);
}
}
void Init(){
memset(head,-1,sizeof(head));
edgenum=0;
memset(R,-1,sizeof(R)); en=0;
memset(pre,-1,sizeof(pre));
//pre[1]=-1;
}
int main(){
int u,v,n,m;//n个点，从1-n
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
Init();
while(--n)
{
scanf("%d %d",&u,&v);
add(u,v); add(v,u);//双向边
}
DFS(1,0);//建以1为根的树 此时深度为0
while(m--)//询问
{
int k; scanf("%d%d%d",&k,&u,&v);
if(k==0)a[u]=v;
else Findans(u,v,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
11 3
1 2 3 4 5 6 7 8 9 10 11
1 4
1 3
2 1
4 5
6 4
3 7
2 9
10 2
10 11
7 8
3 11 8
3 11 9
5 10 5
ans:
8
9
1
////
4 99
1 2 3 4
2 1
3 1
4 1
1 2 4
2 2 4
3 2 4
4 2 4
0 1 100
1 2 4
2 2 4
3 2 4
4 2 4
1 3 3
1 3 1
2 3 1
ans:
4
2
1
in...
100
4
2
in...
3
100
3
//RMQ
//http://blog.csdn.net/liang5630/article/details/7917702
*/