题意：
给出一颗点权树，每次询问两点之间第k大的节点。
题解：
查询时的check条件换成C[u]+C[v]-C[lca]-C[fa[lca]]，其他的和主席树差不多，就是利用前缀和的思想。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; int n,m,q; int a[maxn]; int t[maxn]; int T[maxn*40]; int lson[maxn*40]; int rson[maxn*40];; int c[maxn*40]; int tot; void init_hash () { for (int i=1;i<=n;i++) t[i]=a[i]; sort(t+1,t+n+1); m=unique(t+1,t+n+1)-t-1; } int Hash (int x) { return lower_bound(t+1,t+m+1,x)-t; } int build (int l,int r) { int root=tot++; c[root]=0; if (l!=r) { int mid=(l+r)>>1; lson[root]=build(l,mid); rson[root]=build(mid+1,r); } return root; } int up (int root,int p,int v) { int newRoot=tot++; int tmp=newRoot; int l=1,r=m; while (l<r) { int mid=(l+r)>>1; if (p<=mid) { lson[newRoot]=tot++; rson[newRoot]=rson[root]; newRoot=lson[newRoot]; root=lson[root]; r=mid; } else { rson[newRoot]=tot++; lson[newRoot]=lson[root]; newRoot=rson[newRoot]; root=rson[root]; l=mid+1; } c[newRoot]=c[root]+v; } return tmp; } int query (int left_root,int right_root,int lca_root,int fa_lca,int k) { int l=1,r=m; while (l<r) { int mid=(l+r)>>1; if (c[lson[left_root]]+c[lson[right_root]]-c[lson[lca_root]]-c[lson[fa_lca]]>=k) { r=mid; left_root=lson[left_root]; right_root=lson[right_root]; lca_root=lson[lca_root]; fa_lca=lson[fa_lca]; } else { l=mid+1; k-=(c[lson[left_root]]+c[lson[right_root]]-c[lson[lca_root]]-c[lson[fa_lca]]); left_root=rson[left_root]; right_root=rson[right_root]; lca_root=rson[lca_root]; fa_lca=rson[fa_lca]; } } return l; } vector<int> g[maxn]; int father[30][maxn]; int h[maxn]; void dfs (int u) { for (int v:g[u]) { if (v==father[0][u])continue; T[v]=up(T[u],a[v],1); father[0][v]=u; h[v]=h[u]+1; dfs(v); } } int lca (int x,int y) { if (h[x]<h[y]) swap(x,y); for (int i=20;i>=0;i--) if (h[x]-h[y]>>i) x=father[i][x]; if (x==y) return x; for (int i=20;i>=0;i--) if (father[i][x]!=father[i][y]) { x=father[i][x]; y=father[i][y]; } return father[0][x]; } int main () { scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) scanf("%d",a+i); init_hash(); for (int i=1;i<=n;i++) a[i]=Hash(a[i]); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } T[0]=build(1,m); T[1]=up(T[0],a[1],1); dfs(1); for (int i=1;i<=20;i++) { for (int j=1;j<=n;j++) { father[i][j]=father[i-1][father[i-1][j]]; } } int ans=0; //printf("%d ",father[0][1]); while (q--) { int u,v,k; scanf("%d%d%d",&u,&v,&k); u^=ans; int Lca=lca(u,v); //printf("%d %d %d %d ",u,v,k,Lca); ans=t[query(T[u],T[v],T[Lca],T[father[0][Lca]],k)]; printf("%d ",ans); } }