Lvat_s Blog

很久没更新了呢。

这题我写的是可持久化线段树版本的。

代码参考了hzwer的，orzzzzzzzzzzzz

#include<cstdio>
#include<algorithm>
using namespace std;

long long n,m,h[100005],root[100005],en,lca[100005][20],a[100005],b[100005],deep[100005],es,dfn[100005],pos[100005],dfscnt,cnt,ans=0;

struct Edge{
long long b,next;
}e[200005];

struct SegTree{
long long nl,nr,v;
}tree[3000005];

void Add(long long sa,long long sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

long long LCA(long long u,long long v){
if(deep[u]<deep[v])swap(u,v);
long long sou=deep[u]-deep[v];
for(long long i=0;i<=18;i++)if((1<<i)&sou)u=lca[u][i];
for(long long i=18;i>=0;i--)if(lca[u][i]!=lca[v][i]){u=lca[u][i];v=lca[v][i];}
if(u==v)return u;
return lca[u][0];
}

void DFS(long long u){
dfn[++dfscnt]=u;
pos[u]=dfscnt;
for(long long i=1;i<=18;i++){
    if((1<<i)<=deep[u])lca[u][i]=lca[lca[u][i-1]][i-1];
    else break;
}
for(long long i=h[u];i;i=e[i].next){
    long long v=e[i].b;
    if(lca[u][0]!=v){
        deep[v]=deep[u]+1;
        lca[v][0]=u;
        DFS(v);
    }
}
}

long long Query(long long a,long long bs,long long c){
long long Lca=LCA(a,bs);
//printf("ABCD:%lld %lld %lld %lld\n",pos[a],pos[bs],pos[Lca],pos[lca[Lca][0]]);
long long sa=root[pos[a]],sb=root[pos[bs]],sc=root[pos[Lca]],sd=root[pos[lca[Lca][0]]];
long long l=1,r=es;
while(l<r){
    long long mid=l+r>>1,Sum=tree[tree[sa].nl].v+tree[tree[sb].nl].v-tree[tree[sc].nl].v-tree[tree[sd].nl].v;
    //printf("SUM:%lld\n",Sum);
    if(Sum>=c){r=mid;sa=tree[sa].nl;sb=tree[sb].nl;sc=tree[sc].nl;sd=tree[sd].nl;}
    else {c-=Sum;l=mid+1;sa=tree[sa].nr;sb=tree[sb].nr;sc=tree[sc].nr;sd=tree[sd].nr;}
}
return b[l];
}

void Update(long long l,long long r,long long &root,long long lastroot,long long pos){
root=++cnt;
tree[root].v=tree[lastroot].v+1;
if(l==r)return;
tree[root].nl=tree[lastroot].nl;
tree[root].nr=tree[lastroot].nr;
long long mid=l+r>>1;
if(pos<=mid)Update(l,mid,tree[root].nl,tree[lastroot].nl,pos);
else Update(mid+1,r,tree[root].nr,tree[lastroot].nr,pos);
}

int main(){
freopen("2588.in","r",stdin);
freopen("2588.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(long long i=1;i<=n;i++){
    scanf("%lld",&a[i]);
    b[i]=a[i];
}
sort(b+1,b+n+1);
es=unique(b+1,b+1+n)-b-1;
for(long long i=1;i<=n;i++)a[i]=lower_bound(b+1,b+es+1,a[i])-b;
for(long long i=1;i<n;i++){
    long long sa,sb;
    scanf("%lld %lld",&sa,&sb);
    Add(sa,sb);
    Add(sb,sa);
}
DFS(1);
for(long long i=1;i<=n;i++){
    //printf("ROT:%lld\n",root[pos[lca[dfn[i]][0]]]);
    Update(1,es,root[i],root[pos[lca[dfn[i]][0]]],a[dfn[i]]);
}
for(long long i=1;i<=m;i++){
    long long a,b,c;
    scanf("%lld %lld %lld",&a,&b,&c);
    a^=ans;
    ans=Query(a,b,c);
    if(i!=m)printf("%lld\n",ans);
    else printf("%lld",ans);
}
return 0;
}