我们直接在dfs的时候顺便建主席树 维护一个节点到根路径上的节点出现情况
对于查询(u,v)
用u点的主席树+v点的主席树-lca(u,v)的主席树-lca(u,v)父节点的主席树，在这样产生的主席树上查找第k小的排名，最后输出它原来的点权。
lca我选择了树链剖分
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,m,q,first[N],tot; int a[N],b[N]; struct Edge { int to,next; }edge[2*N]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } int rt[N<<5],lson[N<<5],rson[N<<5],sum[N<<5],cnt; inline int update(int now,int l,int r,int x) { int newnode=++cnt; lson[newnode]=lson[now]; rson[newnode]=rson[now]; sum[newnode]=sum[now]+1; if(l==r) return newnode; int m=(l+r)>>1; if(x<=m) lson[newnode]=update(lson[newnode],l,m,x); else rson[newnode]=update(rson[newnode],m+1,r,x); return newnode; } int father[N],depth[N],size[N],maxson[N]; void dfs1(int now,int fa) { father[now]=fa; depth[now]=depth[fa]+1; size[now]=1; rt[now]=update(rt[father[now]],1,q,a[now]); for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs1(vis,now); size[now]+=size[vis]; if(size[vis]>size[maxson[now]]) maxson[now]=vis; } } int top[N]; void dfs2(int now,int topf) { top[now]=topf; if(maxson[now]) dfs2(maxson[now],topf); for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==father[now]||vis==maxson[now]) continue; dfs2(vis,vis); } } inline int lca(int x,int y) { while(top[x]!=top[y]) { if(depth[top[x]]>=depth[top[y]]) x=father[top[x]]; else y=father[top[y]]; } if(depth[x]>=depth[y]) return y; else return x; } inline int query(int rt1,int rt2,int rt3,int rt4,int l,int r,int k) { if(l==r) return l; int m=(l+r)>>1; int tmp=sum[lson[rt1]]+sum[lson[rt2]]-sum[lson[rt3]]-sum[lson[rt4]]; if(tmp>=k) return query(lson[rt1],lson[rt2],lson[rt3],lson[rt4],l,m,k); else return query(rson[rt1],rson[rt2],rson[rt3],rson[rt4],m+1,r,k-tmp); } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]; } sort(b+1,b+n+1); q=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+1+q,a[i])-b; } for(int i=1;i<n;i++) { int x,y; cin>>x>>y; addedge(x,y); addedge(y,x); } dfs1(1,0); dfs2(1,1); int ans=0; while(m--) { int x,y,z,LCA; cin>>x>>y>>z; x^=ans; LCA=lca(x,y); ans=b[query(rt[x],rt[y],rt[LCA],rt[father[LCA]],1,q,z)]; cout<<ans<<endl; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9810106.html
