题目链接：https://www.spoj.com/problems/COT/en/
题意：给你一颗数，树上每个节点都要一个权值，问你u，v结点这条路径上第k大是多少。
思路：先建立主席树，可知儿子的主席树是由fa数组得到的，并且要更新。
#include<algorithm> #include<cstdio> #include<iostream> #include<vector> #include<cstring> #include<map> #include<queue> #include<cmath> using namespace std; #define ll long long int vector<int> Graph[100005]; int root[100005],top,sum[8000005]; int lson[8000005],rson[8000005]; int a[100005],b[100005],num[100005],n,m; int len,d[100005]; int f[100005][25],t; void bfs() { queue<int>q; q.push(1); d[1]=1; while(q.size()) { int x=q.front(); q.pop(); for(int i=0;i<Graph[x].size();i++) { int y=Graph[x][i]; if(x==y||d[y]) continue; d[y]=d[x]+1; f[y][0]=x; for(int j=1;j<=t;j++) f[y][j]=f[f[y][j-1]][j-1]; q.push(y); } } } int lca(int x,int y) { if(d[x]>d[y]) swap(x,y); for(int i=t;i>=0;i--) if(d[f[y][i]]>= d[x]) y=f[y][i]; if(x==y) return x; for(int i=t;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } void Build(int &rt,int l,int r) { rt=++top; lson[rt]=0; rson[rt]=0; sum[rt]=0; if(l==r) return; int mid=(l+r)>>1; Build(lson[rt],l,mid); Build(rson[rt],mid+1,r); } void Update(int &ne,int last,int l,int r,int pos) { ne=++top; sum[ne]=sum[last]+1; lson[ne]=lson[last]; rson[ne]=rson[last]; if(l==r) return; int mid=(l+r)>>1; if(pos<=mid) Update(lson[ne],lson[last],l,mid,pos); else Update(rson[ne],rson[last],mid+1,r,pos); } void dfs(int x,int fa) { Update(root[x],root[fa],1,len,num[x]); for(int i=0;i<Graph[x].size();i++) { int y=Graph[x][i]; if(y==fa) continue; dfs(y,x); } } int Query(int x,int y,int f,int fa,int k,int l,int r) { if(l==r) return l; int ans=sum[lson[x]]+sum[lson[y]]-sum[lson[f]]-sum[lson[fa]]; int mid=(l+r)>>1; if(k<=ans) return Query(lson[x],lson[y],lson[f],lson[fa],k,l,mid); else return Query(rson[x],rson[y],rson[f],rson[fa],k-ans,mid+1,r); } void init() { memset(f,0,sizeof(f)); top=0; for(int i=0;i<=n;i++) Graph[i].clear(); } int main() { while(~scanf("%d%d",&n,&m)) { init(); t=(int)(log(n)/log(2))+1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); len=unique(b+1,b+n+1)-(b+1); for(int i=1;i<=n;i++) num[i]=lower_bound(b+1,b+len+1,a[i])-b; for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); Graph[u].push_back(v); Graph[v].push_back(u); } bfs(); Build(root[0],1,len); dfs(1,0); while(m--) { int x,y,k; scanf("%d%d%d",&x,&y,&k); int fa = lca(x,y); int ans = Query(root[x],root[y],root[fa],root[f[fa][0]],k,1,len); printf("%d ",b[ans]); } } return 0; }