题解：跟数组求第K大差不多,这个要求下求下lca,然后区间查询的应该是sum[u]+sum[v]-sum[lca(u,v)]-sum[f[lac(u,v)][0]];
You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.
We will ask you to perform the following operation:
- u v k : ask for the kth minimum weight on the path from node u to node v
Input
In the first line there are two integers N and M. (N, M <= 100000)
In the second line there are N integers. The ith integer denotes the weight of the ith node.
In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).
In the next M lines, each line contains three integers u v k, which means an operation asking for the kth minimum weight on the path from node u to node v.
Output
For each operation, print its result.
Example
Input: 8 5 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
Output: 2
8
9
105
7
#include<bits/stdc++.h> #include<set> #include<cstdio> #include<iomanip> #include<iostream> #include<string> #include<cstring> #include<algorithm> #define pb push_back #define ll long long #define PI 3.14159265 //#define ls l,m,rt<<1 //#define rs m+1,r,rt<<1|1 #define eps 1e-7 typedef unsigned long long ull; const int mod=1e9+9; const ll inf=0x3f3f3f3f3f3f3f; const int maxn=1e5+5; using namespace std; int a[maxn],b[maxn],head[maxn],sum[maxn*30],rt[maxn],dep[maxn],f[maxn][20],n,m,tol,sz; int ls[maxn*30],rs[maxn*30],tot; struct edge { int to,next; }eg[maxn*4]; void add_edge(int u,int v) { eg[tol].to=v; eg[tol].next=head[u]; head[u]=tol++; } void dfs(int v,int d,int p) { f[v][0]=p; dep[v]=d; for(int i=head[v];i!=-1;i=eg[i].next) { if(eg[i].to!=p)dfs(eg[i].to,d+1,v); } } void init(int c) { dfs(1,0,0); for(int k=0;k<19;k++) { for(int i=1;i<=c;i++) { if(f[i][k]==0)f[i][k+1]=0; else f[i][k+1]=f[f[i][k]][k]; } } } void update(int &o,int pre,int l,int r,int x) { o=++tot; ls[o]=ls[pre]; rs[o]=rs[pre]; sum[o]=sum[pre]+1; int m=(l+r)>>1; if(l==r)return ; if(x<=m)update(ls[o],ls[pre],l,m,x); else update(rs[o],rs[pre],m+1,r,x); } void dfs1(int v,int p) { update(rt[v],rt[p],1,sz,a[v]); for(int i=head[v];i!=-1;i=eg[i].next) { if(eg[i].to!=p)dfs1(eg[i].to,v); } } int lca(int u,int v) { if(dep[u]>dep[v])swap(u,v); for(int i=0;i<20;i++) { if(dep[v]-dep[u]>>i&1)v=f[v][i]; } if(v==u)return v; for(int i=19;i>=0;i--) { if(f[v][i]!=f[u][i]) { u=f[u][i]; v=f[v][i]; } } return f[v][0]; } void build(int &o,int l,int r) { o=++tot; sum[o]=0; if(l==r)return; int m=(l+r)>>1; build(ls[o],l,m); build(rs[o],m+1,r); } int query(int l,int r,int k,int pu,int pv,int pl,int pfl) { if(l==r)return l; int m=(l+r)>>1; int cnt=sum[ls[pu]]+sum[ls[pv]]-sum[ls[pl]]-sum[ls[pfl]]; if(cnt>=k)return query(l,m,k,ls[pu],ls[pv],ls[pl],ls[pfl]); else return query(m+1,r,k-cnt,rs[pu],rs[pv],rs[pl],rs[pfl]); } int main() { while(~scanf("%d %d",&n,&m)) { memset(head,-1,sizeof(head));tot=0;tol=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]);b[i]=a[i]; } sort(b+1,b+n+1); sz=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+1+sz,a[i])-b; } for(int i=0;i<n-1;i++) { int u,v; scanf("%d %d",&u,&v); add_edge(u,v); add_edge(v,u); } init(n); build(rt[0],1,sz); dfs1(1,0); while(m--) { int u,v,k; scanf("%d %d %d",&u,&v,&k); int lc=lca(v,u); // cout<<lc<<"*"<<endl; int id=query(1,sz,k,rt[u],rt[v],rt[lc],rt[f[lc][0]]); printf("%d ",b[id]); } } return 0; }