Description:

给定一棵树,每次询问某点子树中到其不超过k的所有点的最小点权

强制在线

Hint:

\(n,m\le 10^5\)

Solution:

看到题目第一反应是以深度为下标,dfs序为版本建树

然而不行,因为min不满足前缀可减

所以我们换过来,每个\(dep\)建树表示\(<=dep\)所有点的权值

在上面直接查x子树的min就好了

貌似这题用线段树合并就是SBT......

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int mxn=5e5+5,inf=1e9;

int n,m,tot,cnt,rk[mxn],hd[mxn];

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}

    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

    return x*f;

}

inline void chkmax(int &x,int y) {if(x<y) x=y;}

inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {

    int to,nxt;

}t[mxn<<1];

inline void add(int u,int v) {

    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;

}

int df,dep[mxn],lst[mxn],dfn[mxn],tr[mxn<<5],ls[mxn<<5],rs[mxn<<5],a[mxn],rt[mxn];

void dfs(int u,int fa) {

    dep[u]=dep[fa]+1; dfn[u]=++df;

    for(int i=hd[u];i;i=t[i].nxt) {

        int v=t[i].to;

        if(v==fa) continue ;

        dfs(v,u);

    }

    lst[u]=df;

}

int cmp(int x,int y) {

    return dep[x]<dep[y];

}

void update(int las,int &p,int l,int r,int pos,int val) {

    p=++tot;

    if(l==r) {tr[p]=min(tr[p],val);return ; }int mid=(l+r)>>1;

    if(pos<=mid) update(ls[las],ls[p],l,mid,pos,val),rs[p]=rs[las];

    else update(rs[las],rs[p],mid+1,r,pos,val),ls[p]=ls[las];

    tr[p]=min(tr[ls[p]],tr[rs[p]]);

} 

int query(int p,int l,int r,int ql,int qr) {

    if(!p) return inf;

    if(ql<=l&&r<=qr) return tr[p];

    int mid=(l+r)>>1; int res=inf;

    if(ql<=mid) chkmin(res,query(ls[p],l,mid,ql,qr));

    if(qr>mid) chkmin(res,query(rs[p],mid+1,r,ql,qr));

    return res;

}

int r;

int main()

{

    n=read(); r=read(); int u,v,p,q; memset(tr,0x3f,sizeof(tr));

    for(int i=1;i<=n;++i) rk[i]=i,a[i]=read();

    for(int i=1;i<n;++i) {

        u=read(); v=read();

        add(u,v); add(v,u);

    }

    dfs(r,0); int ans=0;

    sort(rk+1,rk+n+1,cmp);

    for(int i=1;i<=n;++i)

        update(rt[dep[rk[i-1]]],rt[dep[rk[i]]],1,n,dfn[rk[i]],a[rk[i]]);

    m=read();

    for(int i=1;i<=m;++i) {

        p=(read()+ans)%n+1; q=(read()+ans)%n;

        printf("%d\n",ans=query(rt[min(dep[p]+q,dep[rk[n]])],1,n,dfn[p],lst[p])); //注意特判深度超出最大深度

    }

    return 0;

}