牛客挑战赛42 C-一道 ♂ 题（蒟蒻见解）

小睿睿的兄弟

https://ac.nowcoder.com/acm/contest/6944/C

C - 小睿睿的兄弟

题目大意（划重点）

有一棵树,肯定要跑一遍啊
求x的第k代兄弟,说明他肯定要有这个祖先而且兄弟得有这么多
还要求k小值（giao）,怎么这么麻烦

分析问题（现在没有探讨珂学）

首先得有一个全局思想(我要求什么,怎么求)
我们要求一个k祖先,所以记录一个数组f[i][j],表示点j的(1<<i)代祖先
解决这个问题的关键一步,是想出怎么求出x的兄弟,因为他们虽然可能在同一层,但是有可能没有共同的k代祖先

但是可以发现,如果我们以深度为第一关键字,遍历顺序为第二关键字,开一个vector存储每一个深度对应的节点,就可以保证这些节点的有序,所以还要在遍历树时建立一个时间戳,就像这样

可以发现的是,只要对于某个x的第k代祖先,我们在时间戳为dfn[k]~dfn[k]+siz[k]-1的范围内寻找就不会找到在其他子树上处于同一深度的节点
然后就是k小值,难道是暴力枚举,然后sort排序?怎么可能,我们可以以深度为序,对每个点建立一棵树(主席树),不会的话可以去敲敲模板

代码

我们分开放

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,tot,cnt,idx,scc;
int h[N],nex[N<<1],ver[N<<1],val[N];
int dfn[N],dep[N],siz[N],f[20][N];
int lc[N],rc[N],rt[N],id[N],s[N];
vector<int>t[N];
//记录深度为i的点有多少个 
/*********跑图部分*********/
inline int god(int x,int y)
{
    if(dep[x]==dep[y]) return dfn[x]<dfn[y];
    return dep[x]<dep[y];
}
inline void add(int x,int y)
{
    nex[tot]=h[x];
    ver[tot]=y;
    h[x]=tot++;
}
inline void dfs(int u,int v)
{
        siz[u]=1;dep[u]=dep[v]+1;
        f[0][u]=v;dfn[u]=++idx;
    //时间戳记顺序 
    for (int i=1;i<=18;i++)
        f[i][u]=f[i-1][f[i-1][u]];

    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        dfs(j,u);
        siz[u]+=siz[j];
    }
}//dfs跑节点 
inline int lca(int k,int x)
{
    for (int i=20;i>=0;i--)
        if(k&(1<<i))
            x=f[i][x];

    return x;
}//求出祖先 
/*******建树部分*********/
inline void build(int l,int r,int &now)
{
    now=++scc;
    s[now]=0;

    if(l==r) return ;

    int mid=(l+r)>>1;
    build(l,mid,lc[now]);build(mid+1,r,rc[now]);
}
inline void ins(int l,int r,int las,int &pas,int x)
{
    pas=++scc;
    lc[pas]=lc[las];rc[pas]=rc[las];
    s[pas]=s[las]+1;

    if(l==r) return ;

    int mid=(l+r)>>1;
    if(x<=mid) ins(l,mid,lc[las],lc[pas],x);
    else ins(mid+1,r,rc[las],rc[pas],x);
}/*插入新值*/
inline int ask(int l,int r,int x,int y,int k)
{
    if(l==r) return l;

    int sum=s[lc[y]]-s[lc[x]];
    int mid=(l+r)>>1;
    if(sum<k) return ask(mid+1,r,rc[x],rc[y],k-sum);
    else return ask(l,mid,lc[x],lc[y],k);
}//经典的区间求k小值
inline void pre()
{
    for (int i=1;i<=n;i++) rt[i]=i;
    sort(rt+1,rt+n+1,god);
    //排序原因 :拥有同一个k祖先的是一群连续的点 
    for (int i=1;i<=n;i++)
        t[dep[rt[i]]].push_back(rt[i]);
    //记录每个深度的节点 
    int max_dep=0;
    for (int i=1;i<=n;i++)
        max_dep=max(max_dep,dep[i]);
    build(1,n,rt[0]);//建立初始的树
    for (int i=1;i<=max_dep;i++)
    {
        int len=t[i].size();
        for (int j=0;j<len;j++)
        {
            int p=t[i][j];
            id[p]=++cnt;
            ins(1,n,rt[cnt-1],rt[cnt],val[p]);
        }
    }
}
int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    for (int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);pre();

    int las=0;
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);x=(x^las)%n+1;

        if(dep[x]<=y)
        {
            puts("?");
            continue;
        }
        int op=lca(y,x);

        int lk=0,rk=0;
        int lm=dfn[op],rm=dfn[op]+siz[op]-1,now=dep[op]+y;
        int l=0,r=t[now].size()-1;
        while(l<=r)
        {
            int uo=(l+r)>>1;
            int mid=dfn[t[now][uo]];
            if(mid<lm) l=uo+1;
            else lk=t[now][uo],r=uo-1;
        }

        l=0,r=t[now].size()-1;
        while(l<=r)
        {
            int uo=(l+r)>>1;
            int mid=dfn[t[now][uo]];
            if(mid>rm) r=uo-1;
            else rk=t[now][uo],l=uo+1;
        }//二分两次,找到对应的区间

        if(id[rk]-id[lk]+1<y)
        {
            puts("?");
            continue;
        }
        las=ask(1,n,rt[id[lk]-1],rt[id[rk]],y);

        printf("%d\n",las);
    }

    return 0;
}