比较经典的树上主席树，然而改了半天，tmd发现线段树开大了导致TLE？？？？？这TM都能T？醉了，虽然我知道开大空间可能会T，但没想到有一天自己亲身成为实验体QAQ。。
跟普通的主席树其实没什么区别，就是在树上扫一遍顺便建权值线段树，然后最后求答案是sum[x]+sum[y]-sum[lca]-sum[fa[lca]]这个已经老生常谈了就不解释了。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=2e5+5; const int M=5e6+5; int ls[M],rs[M],sum[M]; int f[N][22]; int dep[N],root[N],mi[20]; int fa[N]; int sz,n,m,ans; int head[N],go[N],val[N],next[N]; int a[N],num[N],hash[N],cnt; int tot,id[N]; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } inline int find(int x) { int l=1,r=cnt; while (l<=r) { int mid=(l+r)>>1; if (hash[mid]<x)l=mid+1; else r=mid-1; } return l; } inline int lca(int x,int y) { if (dep[x]<dep[y])swap(x,y); fd(i,16,0) if (dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y)return x; fd(i,16,0) if (f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } return f[x][0]; } inline void dfs(int x,int fat,int depth) { dep[x]=depth; fa[x]=fat; fo(i,1,16) { if (dep[x]-mi[i]<1)break; f[x][i]=f[f[x][i-1]][i-1]; } for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fat) { f[v][0]=x; dfs(v,x,depth+1); } } } inline void update(int &x,int l,int r,int pos,int v) { int last=x; x=++sz; sum[x]=sum[last]+v; ls[x]=ls[last],rs[x]=rs[last]; if (l==r)return; int mid=(l+r)>>1; if (pos<=mid)update(ls[x],l,mid,pos,v); else update(rs[x],mid+1,r,pos,v); } inline void build(int x,int fa) { for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa) { root[v]=root[x]; update(root[v],1,n,num[v],1); build(v,x); } } } inline bool cmp(int x,int y) { return a[x]<a[y]; } inline int query(int a,int b,int c,int d,int l,int r,int k) { int mid=(l+r)>>1; if (l==r)return l; int t=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]]; if (t>=k)return query(ls[a],ls[b],ls[c],ls[d],l,mid,k); else return query(rs[a],rs[b],rs[c],rs[d],mid+1,r,k-t); } int main() { scanf("%d%d",&n,&m); mi[0]=1; fo(i,1,16)mi[i]=mi[i-1]<<1; fo(i,1,n)scanf("%d",&a[i]),id[i]=i; fo(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } sort(id+1,id+1+n,cmp); fo(i,1,n) num[id[i]]=i,hash[i]=a[id[i]]; dfs(1,0,1); update(root[1],1,n,num[1],1); build(1,0); fo(i,1,m) { int l,r,k; scanf("%d%d%d",&l,&r,&k); l^=ans; int Lca=lca(l,r); int flca=fa[Lca]; ans=hash[query(root[l],root[r],root[Lca],root[flca],1,n,k)]; if (i==m)printf("%d",ans); else printf("%d\n",ans); } }