这不线段树合并板子题吗
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
#define re register
#define maxn 100005
#define inf 9999999999
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
inline int max(int a,int b) {return a>b?a:b;}
inline int min(int a,int b) {return a<b?a:b;}
struct E{int v,nxt;}e[maxn<<1];
int l[maxn*40],r[maxn*40],mx[maxn*40];
int tot,rt[maxn];
int n,ro,head[maxn],num,md,deep[maxn],a[maxn];
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
void dfs(int x) {
md=max(md,deep[x]);
for(re int i=head[x];i;i=e[i].nxt) {
if(deep[e[i].v]) continue;
deep[e[i].v]=deep[x]+1;
dfs(e[i].v);
}
}
inline void pushup(int now) {mx[now]=min(mx[l[now]],mx[r[now]]);}
int change(int now,int x,int y,int pos,int val) {
if(!now) now=++tot,mx[now]=inf;
if(x==y) {mx[now]=min(mx[now],val);return now;}
int mid=x+y>>1;
if(pos<=mid) l[now]=change(l[now],x,mid,pos,val);
else r[now]=change(r[now],mid+1,y,pos,val);
pushup(now);return now;
}
int merge(int a,int b,int x,int y) {
if(!a) return b;if(!b) return a;
int now=++tot;
if(x==y) {mx[now]=min(mx[a],mx[b]);return now;}
int mid=x+y>>1;
l[now]=merge(l[a],l[b],x,mid),r[now]=merge(r[a],r[b],mid+1,y);
pushup(now);return now;
}
int query(int now,int x,int y,int lx,int ry) {
if(!now) return inf;
if(x<=lx&&y>=ry) return mx[now];
int mid=lx+ry>>1;
if(y<=mid) return query(l[now],x,y,lx,mid);
if(x>mid) return query(r[now],x,y,mid+1,ry);
return min(query(l[now],x,y,lx,mid),query(r[now],x,y,mid+1,ry));
}
void Dfs(int x) {
for(re int i=head[x];i;i=e[i].nxt) {
if(deep[e[i].v]<deep[x]) continue;
Dfs(e[i].v);
rt[x]=merge(rt[x],rt[e[i].v],1,md);
}
}
int main() {
n=read(),ro=read();
for(re int i=1;i<=n;i++) a[i]=read();
for(re int x,y,i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
deep[ro]=1,dfs(ro);mx[0]=inf;
for(re int i=1;i<=n;i++) rt[i]=change(rt[i],1,md,deep[i],a[i]);
Dfs(ro);
int x,y,Q=read(),lst=0;
while(Q--) {
x=read(),y=read();
x+=lst;x%=n,x++;y+=lst;y%=n;
lst=query(rt[x],deep[x],deep[x]+y,1,md);
printf("%d
",lst);
}
return 0;
}
或许我们还可以直接(dsu on tree)，对(dsu)里的桶可持久化，这样就是空间时间都多一个(log)
主席树的做法巧妙的一批，我们可以以深度为时间轴，以(dfs)序为下标来建树
查询的时候直接查([1,dep_x+k])里(dfn_x<=dfn<=dfn_x+sum_x-1)，由于(dfn)的限制，所以这样的点只会存在于(x)的子树里