路径排名

思路与复杂度

离散化点权，为每个节点保存根到该节点的点权频次主席树。询问用 root[u]+root[v]-root[lca]-root[parent(lca)] 得到路径频次，再根据左右子树计数求第 k 小。树遍历需避免长链递归栈溢出。预处理 O(n log n)，每次询问 O(log n)，空间 O(n log n)。

正确性与边界

四棵频次树的容斥恰好保留路径点权，其中LCA计入一次。

参考代码

#include<bits/stdc++.h>
using namespace std;const int N=200005,L=19;struct Z{int l,r,s;}t[N*22];int rt[N],tot,up[N][L+1],dep[N],a[N],rk[N];vector<int>g[N],v;
int ad(int p,int l,int r,int x){int q=++tot;t[q]=t[p];t[q].s++;if(l<r){int m=(l+r)/2;if(x<=m)t[q].l=ad(t[p].l,l,m,x);else t[q].r=ad(t[p].r,m+1,r,x);}return q;}
void dfs(int u,int f){up[u][0]=f;dep[u]=dep[f]+1;for(int j=1;j<=L;j++)up[u][j]=up[up[u][j-1]][j-1];rt[u]=ad(rt[f],1,v.size(),rk[u]);for(int x:g[u])if(x!=f)dfs(x,u);}
int lc(int x,int y){if(dep[x]<dep[y])swap(x,y);for(int j=L;j>=0;j--)if(dep[up[x][j]]>=dep[y])x=up[x][j];if(x==y)return x;for(int j=L;j>=0;j--)if(up[x][j]!=up[y][j])x=up[x][j],y=up[y][j];return up[x][0];}
int kth(int A,int B,int C,int D,int l,int r,int k){if(l==r)return l;int z=t[t[A].l].s+t[t[B].l].s-t[t[C].l].s-t[t[D].l].s,m=(l+r)/2;if(k<=z)return kth(t[A].l,t[B].l,t[C].l,t[D].l,l,m,k);return kth(t[A].r,t[B].r,t[C].r,t[D].r,m+1,r,k-z);}
int main(){ios::sync_with_stdio(0);cin.tie(0);int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i],v.push_back(a[i]);sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++)rk[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;for(int i=1,x,y;i<n;i++)cin>>x>>y,g[x].push_back(y),g[y].push_back(x);dfs(1,0);while(q--){int x,y,k;cin>>x>>y>>k;int w=lc(x,y),p=up[w][0];cout<<v[kth(rt[x],rt[y],rt[w],rt[p],1,v.size(),k)-1]<<"\n";}}