这题非常好！！！
主席树版本
很简单的题目，给一个按照指定节点的树，树上有点权，你需要回答给定节点的子树中，和其距离不超过k的节点中，权值最小的。
肯定首先一想，按照dfs序列建树，然后按照深度为下标，建立主席树，那么我们通过主席树相间得到区间状态，但是很不幸，区间最值不能通过减去历史版本的主席树得到。
考虑照深度建立主席树，按照dfs下标建立，貌似可以耶！！！
我们直接查询当前节点往下k深度的主席树，它保存的就是从深度为1-到深度为deep[p]+k深度的所有节点的dfs序对应的点权值
我们查询子树对应区间的dfs序的最小值，就是答案啦！！！
主席树的话，不建议最开始去建树初始化，本来就是动态开点了，不用这么麻烦，这个题也是一样，我们建立主席树的时候，直接写一个析构函数初始化最大值即可
不用再buildtree了2333。。。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+;
struct node{
int l,r;
int w;
node(){
w=INF;
}
}tree[maxn*];
struct ID{
int pre,bac;
}id[maxn];
int cnt,tot,dfsorder,mxdep;
int root[maxn*];
int a[maxn],deepth[maxn];
int ver[maxn*],Next[maxn*],head[maxn];
int mp[maxn*];
queue<int>q;
int n,r;
void add(int x,int y){
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
ver[++tot]=x;Next[tot]=head[y];head[y]=tot;
}
void dfs(int u,int fa){
deepth[u]=deepth[fa]+;
id[u].pre=++dfsorder;
mxdep=max(mxdep,deepth[u]);
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(v==fa)continue;
dfs(v,u);
}
id[u].bac=dfsorder;
} void inserts(int l,int r,int pre,int &now,int pos,int w){
now=++cnt;
tree[now]=tree[pre];
tree[now].w=min(tree[now].w,w);
if(l==r){
return;
}
int mid=(l+r)>>;
if(pos<=mid){
inserts(l,mid,tree[pre].l,tree[now].l,pos,w);
}else {
inserts(mid+,r,tree[pre].r,tree[now].r,pos,w);
}
}
int query(int rt,int l,int r,int ql,int qr){
if(ql<=l && r<=qr){
return tree[rt].w;
}
int mid=(l+r)>>;
if (qr<=mid){
return query(tree[rt].l,l,mid,ql,qr);
}else if(ql>mid){
return query(tree[rt].r,mid+,r,ql,qr);
}else {
return min(query(tree[rt].l,l,mid,ql,mid),query(tree[rt].r,mid+,r,mid+,qr));
}
}
void bfs(int s){
q.push(s);
int tmp=;
while(q.size()){
int now=q.front();
q.pop();
inserts(,*n,root[tmp],root[tmp+],id[now].pre,a[now]);
mp[deepth[now]]=++tmp;
for (int i=head[now];i;i=Next[i]){
int nex=ver[i];
if(deepth[nex]==deepth[now]+){
q.push(nex);
}
}
}
}
int main(){
int uu,vv;
while(~scanf("%d%d",&n,&r)){
tot=;
cnt=;
dfsorder=;
mxdep=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for (int i=;i<=n-;i++){
scanf("%d%d",&uu,&vv);
add(uu,vv);
}
dfs(r,);
bfs(r);
int op;
int p,q;
int ans=;
scanf("%d",&op);
while(op--){
scanf("%d%d",&p,&q);
p=(p+ans)%n+,q=(q+ans)%n;
ans=query(root[mp[min(deepth[p]+q,mxdep)]],,n*,id[p].pre,id[p].bac);
printf("%d\n",ans);
}
}
return ;
}
线段树合并方法
在机房搞搞瞎搞了半天，看了半天没怎么懂线段树合并，属实菜。。。
最后再瞄了一眼，嗯，貌似懂了，不就是从每个节点都新建一个线段树，然后两个树，暴力对这两个线段树的每个节点，都去 暴力比较取最小值后，再拆掉以前的节点，用新建节点保存合并之后的信息，然后父亲节点的线段树得到儿子节点的信息。然后？然后就没了哈哈哈哈。
然后这道题就变成一道模版题了，子树的信息可以通过合并得到，而线段树保存的就是以深度为下标的儿子节点的点权最小值。询问的时候，我们只需要询问当前节点的线段树，其线段树内部就包含了儿子节点的信息，然后我们在给定的深度区间进行区间询问最小值，就能得到答案。真~模版题，注意这种线段树合并，由于每个节点都要开线段树，大佬说空间接近o(n*logn)所以线段树还是*40吧。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5+;
struct node{
int l,r;
int w;
node(){
w=INF;
}
}tree[maxx*];
int cnt,tot,maxdeep;
int root[maxx];
int deepth[maxx],ver[maxx*],Next[maxx*],head[maxx];
int a[maxx];
int n,r;
void add(int x,int y){
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
ver[++tot]=x;Next[tot]=head[y];head[y]=tot;
}
void inserts(int &rt,int l,int r,int pos,int w){
rt=++cnt;
tree[rt].w=min(tree[rt].w,w);
if(l==r){
return ;
}
int mid=(l+r)>>;
if(pos<=mid)inserts(tree[rt].l,l,mid,pos,w);
else inserts(tree[rt].r,mid+,r,pos,w);
}
int merge(int x,int y){
if(!x||!y){
return x+y;
}
int tmp=++cnt;
tree[tmp].l=merge(tree[x].l,tree[y].l);
tree[tmp].r=merge(tree[x].r,tree[y].r);
tree[tmp].w=min(tree[x].w,tree[y].w);
return tmp;
}
int query(int rt,int l,int r,int ql,int qr){
if(ql<=l && r<=qr){
return tree[rt].w;
}
int mid=(l+r)>>;
if(qr<=mid){
return query(tree[rt].l,l,mid,ql,qr);
}else if(ql>mid){
return query(tree[rt].r,mid+,r,ql,qr);
}else{
return min(query(tree[rt].l,l,mid,ql,qr),query(tree[rt].r,mid+,r,ql,qr));
}
}
void dfs(int u,int fa){
deepth[u]=deepth[fa]+;
maxdeep=max(maxdeep,deepth[u]);
inserts(root[u],,n,deepth[u],a[u]);
for (int i=head[u];i;i=Next[i]){
int v=ver[i];
if(v==fa)continue;
dfs(v,u);
root[u]=merge(root[u],root[v]);
}
}
int main(){
int uu,vv;
while(~scanf("%d%d",&n,&r)){
maxdeep=;
cnt=;
tot=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=;i<n;i++){
scanf("%d%d",&uu,&vv);
add(uu,vv);
}
int op;
scanf("%d",&op);
dfs(r,);
int ans=;
int p,q;
while(op--){
scanf("%d%d",&p,&q);
p=(p+ans)%n+,q=(q+ans)%n;
ans=query(root[p],,n,deepth[p],min(deepth[p]+q,n));
printf("%d\n",ans);
}
}
return ;
}