http://codeforces.com/problemset/problem/893/F

题意:

n个点的树,r为根

强制在线的询问,以x为根的子树里面,深度<=k(根深度为0)的点的权值最小为多少

=====

解法:

bfs序

对于每个点,维护它深度+(1<<k)以后的l,r(这个区间内都是它在在+1<<k深度的孩子)

例如:

bfs序列是1234567...的完全二叉树

1的l[1]为4 r[1]为8

表示[4,8)这一段里面是1的第二层孩子

而2的l[1]/r[1]为[8,12),l[0]/r[0]为[4,6)

3的l[1]/r[1]为[12,16),l[0]/r[0]为[6,8)

那么,我们用线段树维护区间l,区间r

然后用倍增的思路,先bfs的时候初始化k=0,然后k=1 k=2 ... k=17

同时,val[i][k]也表示第i个点 在它到1<<k的深度以内的最小值

那么可以顺便维护好val[i][k]

每次询问,就用倍增的思路,每次询问一个区间的val的最小值

例如 x=1 深度为6 还是那个二叉树

首先询问 val[1][2] 然后我们要询问val[8..15][1]的最小值

然而在具体实现的时候,因为一些细节问题,我将自己设置为深度1,所以最后只要y++就可以了.....

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int depth[100005];
int a[100005];
int l[1<<18][18];
int r[1<<18][18];
int val[1<<18][18];
int dfn[100005];
int l_l[100005];
int r_r[100005];
int v_v[100005];
struct edge
{
    int y;
    edge * next;
};
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
edge * li[100005];
int fa[100005];
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
void bfs(int s)
{
    memset(dfn,-1,sizeof(dfn));
    static int que[100005];
    int front=0,rail=1;
    que[0]=s;
    dfn[s]=0;
    for (;front<rail;front++)
    {
        edge * t;
        int now=que[front];
        l_l[front]=rail;
        v_v[front]=a[now];
        for (t=li[now];t!=0;t=t->next)
        {
            if (dfn[t->y]!=-1) continue;
            dfn[t->y]=rail;
            que[rail++]=t->y;
        }
        r_r[front]=rail;
        if (l_l[front]==r_r[front])
        {
            l_l[front]=1000000;
            r_r[front]=-1;
        }
    }
}
int query(int num,int ll,int rr,int l0,int r0,int i)
{
    if (l0>=r0) return 1000000000;
    if ((l0<=ll)&&(rr<=r0))
    {
        return val[num][i];
    }
    int mid=(ll+rr)/2;
    int ans=1000000000;
    if (l0<mid) ans=min(ans,query(num*2+1,ll,mid,l0,r0,i));
    if (mid<r0) ans=min(ans,query(num*2+2,mid,rr,l0,r0,i));
    return ans;
}
int query_l(int num,int ll,int rr,int l0,int r0,int i)
{
    if (l0>=r0) return 1000000;
    if ((l0<=ll)&&(rr<=r0))
    {
        return l[num][i];
    }
    int mid=(ll+rr)/2;
    int ans=1000000;
    if (l0<mid) ans=min(ans,query_l(num*2+1,ll,mid,l0,r0,i));
    if (mid<r0) ans=min(ans,query_l(num*2+2,mid,rr,l0,r0,i));
    return ans;
}
int query_r(int num,int ll,int rr,int l0,int r0,int i)
{
    if (l0>=r0) return -1;
    if ((l0<=ll)&&(rr<=r0))
    {
        return r[num][i];
    }
    int mid=(ll+rr)/2;
    int ans=-1;
    if (l0<mid) ans=max(ans,query_r(num*2+1,ll,mid,l0,r0,i));
    if (mid<r0) ans=max(ans,query_r(num*2+2,mid,rr,l0,r0,i));
    return ans;
}
void build_tree(int num,int ll,int rr)
{
    if (ll==rr-1)
    {
        val[num][0]=v_v[ll];
        l[num][0]=l_l[ll];
        r[num][0]=r_r[ll];
        return;
    }
    int mid=(ll+rr)/2;
    build_tree(num*2+1,ll,mid);
    build_tree(num*2+2,mid,rr);
    val[num][0]=min(val[num*2+1][0],val[num*2+2][0]);
    l[num][0]=min(l[num*2+1][0],l[num*2+2][0]);
    r[num][0]=max(r[num*2+1][0],r[num*2+2][0]);
}
int n;
void build_tree2(int num,int ll,int rr,int i)
{
    if (ll==rr-1)
    {
        l[num][i]=query_l(0,0,n,l[num][i-1],r[num][i-1],i-1);
        r[num][i]=query_r(0,0,n,l[num][i-1],r[num][i-1],i-1);
        val[num][i]=min(val[num][i-1],query(0,0,n,l[num][i-1],r[num][i-1],i-1));
        return;
    }
    int mid=(ll+rr)/2;
    build_tree2(num*2+1,ll,mid,i);
    build_tree2(num*2+2,mid,rr,i);
    val[num][i]=min(val[num*2+1][i],val[num*2+2][i]);
    l[num][i]=min(l[num*2+1][i],l[num*2+2][i]);
    r[num][i]=max(r[num*2+1][i],r[num*2+2][i]);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int r;
    scanf("%d%d",&n,&r);
    r--;
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        insert_edge(x,y);
    }
    bfs(r);
    int m;
    scanf("%d",&m);
    int last_ans=0;
    build_tree(0,0,n);
    for (i=1;i<=17;i++)
    {
        build_tree2(0,0,n,i);
    }
    for (i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x=(x+last_ans)%n;
        y=(y+last_ans)%n;
        int i;
        int ans=a[x];
        int nowl=dfn[x];
        int nowr=dfn[x]+1;
        y++;
        for (i=17;i>=0;i--)
        {
            if ((1<<i)&y)
            {
                y^=(1<<i);
                int lastl=nowl;
                int lastr=nowr;
                ans=min(ans,query(0,0,n,nowl,nowr,i));
                nowl=query_l(0,0,n,lastl,lastr,i);
                nowr=query_r(0,0,n,lastl,lastr,i);
            }
        }
        printf("%d\n",ans);
        last_ans=ans;
    }
    return 0;
}