題意：給定一棵n個節點的樹，有n-1條邊；有m個詢問，每個詢問求出給出兩個點路徑上第k大的值
(N, M <= 100000)
Description
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
解題思路：
LCA+主席樹
具體做法：
1. 先周遊整棵樹（dfs或bfs），然後在每個節點上建立一棵線段樹，構成一顆主席樹；
2. 先離散化，對于詢問(u,v,k)，答案就是root[a]+root[b]-root[lca(a,b)]-root[fa[lca(a,b)]]上的第k大。(root[i]表示以節點i上建立的線段樹的根）
#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct node
{
int to,nxt;
}edge[N<<2];
int n,m,tot=0,head[N],dep[N],fa[N][25],pre[N],q[N],a[N],lisan[N];
int root[N<<5],L[N<<5],R[N<<5],cnt=0,sum[N<<5];
void add(int u,int v)
{
edge[++tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot;
}
void bfs(int s)//周遊整棵樹，進行預處理
{
q[1]=s;
dep[s]=0;
fa[s][0]=0;
pre[s]=0;
int l=1,r=2;
while (l<r)
{
int u=q[l];
l++;
for (int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for (int i=head[u];i!=-1;i=edge[i].nxt)
{
int v=edge[i].to;
if (v==pre[u]) continue;
pre[v]=u;
fa[v][0]=u;
dep[v]=dep[u]+1;
q[r]=v;
r++;
}
}
}
int LCA(int x,int y)//LCA打錯，調了幾個小時
{
if (dep[x]<dep[y]) swap(x,y);
for (int i=0;i<=20;i++) if ((dep[x]-dep[y])&(1<<i)) x=fa[x][i];
if (x==y) return x;
for (int i=20;i>=0;i--)
{
if (fa[x][i]!=fa[y][i])
{
x=fa[x][i]；
y=fa[y][i];
}
}
return fa[x][0];
}
int build(int l,int r)//以下三個函數是分别是主席樹的建樹，添加新線段樹，查詢
{
int rt=++cnt;
sum[rt]=0;
if (l>=r) return rt;
int mid=(l+r)>>1;
L[rt]=build(l,mid);
R[rt]=build(mid+1,r);
return rt;
}
int update(int pre,int l,int r,int x)
{
int rt=++cnt;
sum[rt]=sum[pre]+1;
L[rt]=L[pre];
R[rt]=R[pre];
if (l==r) return rt;
int mid=(l+r)>>1;
if (x<=mid) L[rt]=update(L[pre],l,mid,x);
else R[rt]=update(R[pre],mid+1,r,x);
return rt;
}
int query(int l,int r,int k,int nl,int nr,int l1,int l2)
{
if (l==r) return lisan[l];
int mid=(l+r)>>1;
if (sum[L[nl]]+sum[L[nr]]-sum[L[l1]]-sum[L[l2]]<k)
{
k-=sum[L[nl]]+sum[L[nr]]-sum[L[l1]]-sum[L[l2]];
return query(mid+1,r,k,R[nl],R[nr],R[l1],R[l2]);
}
else return query(l,mid,k,L[nl],L[nr],L[l1],L[l2]);
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
lisan[i]=a[i];
}
sort(lisan+1,lisan+n+1);//離散化
int size=unique(lisan+1,lisan+n+1)-lisan-1;
for (int i=1;i<=n;i++) a[i]=lower_bound(lisan+1,lisan+size+1,a[i])-lisan;
for (int i=1;i<=n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
bfs(1);
root[0]=build(1,size);
for (int i=1;i<=n;i++) root[q[i]]=update(root[pre[q[i]]],1,size,a[q[i]]);//建樹
while (m--)
{
int l,r,k,lca;
scanf("%d%d%d",&l,&r,&k);
lca=LCA(l,r);
printf("%d\n",query(1,size,k,root[l],root[r],root[lca],root[pre[lca]]));
}
return 0;
}