Description
给你一颗有根树，点有权值，m次询问，每次问你某个点的子树中距离其不超过k的点的权值的最小值。（边权均为1，点权有可能重复，k值每次询问有可能不同，强制在线）
Input
第一行两个数，为点数$n$和树根$r$。
第二行$n$个数，为每个点的权值。
后面$n-1$行给出树边
再一行$m$，后面给出$m$组询问。
Output
一行答案。
Sample Input
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3
Sample Output
2
5
Solution
线段树合并板子题。注意数组大小QAQ我老是开小$RE$……
感觉$Slr$和$beretty$两个人数据结构学傻了用了另一个题非常麻烦的做法写的这个题……
Code
#include<iostream>
#include<cstdio>
#define N (100009)
using namespace std; struct Sgt{int ls,rs,min;}Segt[N<<];
struct Edge{int to,next;}edge[N<<];
int n,m,sgt_num,ans,lastans,u,v,p,q,r;
int a[N],Root[N],Depth[N];
int head[N],num_edge; void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} void Update(int &now,int l,int r,int x,int v)
{
if (!now) now=++sgt_num;
Segt[now].min=2e9;
if (l==r) {Segt[now].min=v; return;}
int mid=(l+r)>>;
if (x<=mid) Update(Segt[now].ls,l,mid,x,v);
else Update(Segt[now].rs,mid+,r,x,v);
int ls=Segt[now].ls, rs=Segt[now].rs;
Segt[now].min=min(Segt[ls].min,Segt[rs].min);
} int Merge(int x,int y)
{
if (!x || !y) return x|y;
int tmp=++sgt_num;
Segt[tmp].ls=Merge(Segt[x].ls,Segt[y].ls);
Segt[tmp].rs=Merge(Segt[x].rs,Segt[y].rs);
Segt[tmp].min=min(Segt[x].min,Segt[y].min);
return tmp;
} void DFS(int x,int fa)
{
Depth[x]=Depth[fa]+;
Update(Root[x],,n,Depth[x],a[x]);
for (int i=head[x]; i; i=edge[i].next)
if (edge[i].to!=fa)
{
DFS(edge[i].to,x);
Root[x]=Merge(Root[x],Root[edge[i].to]);
}
} int Query(int now,int l,int r,int l1,int r1)
{
if (l>r1 || r<l1) return 2e9;
if (l1<=l && r<=r1) return Segt[now].min;
int mid=(l+r)>>, ls=Segt[now].ls, rs=Segt[now].rs;
return min(Query(ls,l,mid,l1,r1),Query(rs,mid+,r,l1,r1));
} int main()
{
Segt[].min=2e9;
scanf("%d%d",&n,&r);
for (int i=; i<=n; ++i)
scanf("%d",&a[i]);
for (int i=; i<=n-; ++i)
{
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
DFS(r,);
scanf("%d",&m);
for (int i=; i<=m; ++i)
{
scanf("%d%d",&p,&q);
p=(p+lastans)%n+; q=(q+lastans)%n;
ans=Query(Root[p],,n,Depth[p],Depth[p]+q);
printf("%d\n",ans); lastans=ans;
}
}