题目链接:
solution:
LCA好题.询问第k大,不难想到主席树和前缀和思想,对于每个点$x$,我们可以用主席树维护root到$x$上的序列,然后查询$x,y$路径上的第$k$小只需要用前缀和维护权值线段树,用$x+y-lca(x,y)-f[lca(x,y)]$差分即可.
code:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #define R register #define next bmdsaljdk #define debug puts("mlg") #define maxn 110000 using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; inline ll read(); inline void write(ll x); inline void writeln(ll x); inline void writesp(ll x); ll n,m,last; ll q,rt[maxn],val[maxn],lsh[maxn],ls[maxn<<5],rs[maxn<<5],sum[maxn<<5],cnt; ll d[maxn],f[maxn][20]; ll head[maxn<<1],next[maxn<<1],tot,to[maxn<<1]; inline void add(ll x,ll y){to[++tot]=y;next[tot]=head[x];head[x]=tot;} inline void build(ll &Rt,ll l,ll r){Rt=++cnt;if(l==r) return;ll mid=l+r>>1;build(ls[Rt],l,mid);build(rs[Rt],mid+1,r);} inline ll update(ll fa,ll l,ll r,ll p){ll Rt=++cnt;ls[Rt]=ls[fa];rs[Rt]=rs[fa];sum[Rt]=sum[fa]+1;if(l==r) return Rt;ll mid=l+r>>1;if(p<=mid) ls[Rt]=update(ls[Rt],l,mid,p);else rs[Rt]=update(rs[Rt],mid+1,r,p);return Rt;} inline ll query(ll _,ll __,ll ___,ll ____,ll l,ll r,ll k){if(l==r) return l;ll mid=l+r>>1,_____=sum[ls[_]]+sum[ls[__]]-sum[ls[___]]-sum[ls[____]];if(k<=_____) return query(ls[_],ls[__],ls[___],ls[____],l,mid,k);else return query(rs[_],rs[__],rs[___],rs[____],mid+1,r,k-_____);} inline void dfs(ll x,ll fa,ll deep){d[x]=deep;f[x][0]=fa;rt[x]=update(rt[fa],1,q,lower_bound(lsh+1,lsh+q+1,val[x])-lsh);for(R ll i=head[x],ver;i;i=next[i]){ver=to[i];if(ver==fa) continue;dfs(ver,x,deep+1);}} inline void bz(){for(R ll k=1;k<20;k++)for(R ll i=1;i<=n;i++)f[i][k]=f[f[i][k-1]][k-1];} inline void work(){for(R ll i=1;i<=n;i++)lsh[i]=val[i]=read();sort(lsh+1,lsh+n+1);q=unique(lsh+1,lsh+n+1)-lsh-1;build(rt[0],1,q);for(R ll i=1,x,y;i<n;i++){x=read();y=read();add(x,y);add(y,x);}dfs(1,0,1);bz();} inline ll lca(ll x,ll y){if(d[x]<d[y]) swap(x,y);for(R ll i=19;i>=0;i--){if(d[f[x][i]]>=d[y]) x=f[x][i];}if(x==y) return x;for(R ll i=19;i>=0;i--){if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];} inline void Query(){while(m--){ll x=(read()^last),y=read(),z=lca(x,y),u=f[z][0],k=read();writeln(last=lsh[query(rt[x],rt[y],rt[z],rt[u],1,q,k)]);}} int main(){ n=read();m=read(); work(); Query(); } inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;} inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');} inline void writesp(ll x){write(x);putchar(' ');} inline void writeln(ll x){write(x);putchar(' ');}