CF208E Blood Cousins(线段树合并)题解

发布于 2021-10-19  40 次阅读


题目大意

给你一片 $n$ 个点的森林,$m$ 次询问,每次询问一个点 $v_i$ 与多少个点拥有共同的 $p_i$ 级祖先。

$1 \le n,m \le 10^5, 1 \le v_i,p_i \le n$。

解题思路

直接求一个节点的 $k$ 级兄弟肯定不好做,我们考虑把询问转化成一个祖先有多少个 $k$ 级儿子,只要求出 $k$ 级儿子个数再 $-1$ 就是答案了。

因此我们先倍增预处理,然后每次读入询问,用倍增跳 $k$ 级祖先,把询问挂到祖先上。

完成问题的转化后,我们直接以深度建立线段树合并维护每个深度的儿子出现几个,每次如果发现当前节点 $x$ 有被挂询问就单点查询深度为 $dep_x+k$ 的有几个。

于是就做完......了?

确实做完了,不过我们还可以优化!

首先我们倍增求 $k$ 级祖先显然不太彳亍。时间复杂度问题倒是不大,但是空间复杂度 $O(n \log⁡ n)$ 却是比较大的,考虑进行优化。我们知道 $LCA$ 除了倍增也可以用树剖求。那我们考虑用树剖求 $k$ 级祖先。每次跳一条重链,就把 $k$ 减去这条重链的长度,也就是 $dfn_x-dfn_{top_x}$(这里不用 $+1$是因为我们这条重链之后跳的是 $fa_{top_x}$,具体细节还是写代码的时候结合样例琢磨亿下)。如果发现 $k$ 已经不到这条重链的长度了,我们直接返回这条重链上从下往上的第 $k$ 个点(具体细节还是自己定),因为重链上的节点编号是连续的。 时间复杂度显然是预处理 $O(n)$ ,单次处理 $O(\log⁡ n)$ 的,空间复杂度大常数 $O(n)$。

不过树剖的两遍 $dfs$ 需要很多数组!我们可以使用离线 $dfs$ 来整体 $O(n)$ 解决这个问题。只需要使用一个栈,维护从根节点到当前节点的路径,对于一个询问,直接在栈中找到栈顶向下的第 $k$ 个值即可。

这也是一个冷门的套路,不过非常好用,而且只需要一个数组!

然后考虑优化线段树合并,我们按照 $siz$ 从大到小遍历孩子并合并,每次在合并线段树后把旧的线段树的无用节点回收即可。这样可以把空间复杂度优化一些。

Code

这里提供最朴实的倍增做法的代码,以及其他两种做法的部分代码。

朴实做法:

#include<bits/stdc++.h>
using namespace std;
const int N=200005,LogN=20;

bool St;

struct Edge{
    int vet,nxt;
}e[N<<1];

struct Ques{
    int val,ord;
};

struct Node{
    int lson,rson;
    int cnt;
}tree[N*LogN];

int n,m,edge=0,logN=0,head[N];
int fa[N][LogN],dep[N];
int ans[N],rt[N],cntNode=0;
bool isrt[N];
vector <Ques> q[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

inline void dfs(int x,int fath){
    fa[x][0]=fath; dep[x]=dep[fath]+1;
    for (int i=1;i<=logN;++i)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==fath) continue;
        dfs(v,x);
    }
}

inline int jump(int x,int k){
    for (int i=logN;i>=0;--i)
        if ((1<<i)<=k)
            k-=(1<<i),x=fa[x][i];
    return x;
}

#define lid (tree[id].lson)
#define rid (tree[id].rson)

inline void pushup(int id){
    tree[id].cnt=tree[lid].cnt+tree[rid].cnt;
}

inline void Insert(int& id,int l,int r,int val){
    if (!id) id=++cntNode;
    if (l==r){
        // printf("Ins dep=%d\n",l);
        ++tree[id].cnt;
        return void();
    }
    int mid=(l+r)>>1;
    if (val<=mid) Insert(lid,l,mid,val);
    else Insert(rid,mid+1,r,val);
    pushup(id);
}

inline int Merge(int x,int y,int l,int r){
    if (!x) return y;
    if (!y) return x;
    if (l==r){
        tree[x].cnt+=tree[y].cnt;
        return x;
    }
    int mid=(l+r)>>1;
    tree[x].lson=Merge(tree[x].lson,tree[y].lson,l,mid);
    tree[x].rson=Merge(tree[x].rson,tree[y].rson,mid+1,r);
    pushup(x);
    return x;
}

inline int Query(int id,int l,int r,int val){
    if (!id) return 0;
    if (l>r) return 0;
    if (l==r){
        // printf("Qry dep=%d\n",l);
        return tree[id].cnt;
    }
    int mid=(l+r)>>1;
    if (val<=mid) return Query(lid,l,mid,val);
    else return Query(rid,mid+1,r,val);
}

inline void Dfs(int x,int fath){
    // printf("x=%d fath=%d dep[x]=%d\n",x,fath,dep[x]);
    rt[x]=++cntNode;
    Insert(rt[x],1,n+1,dep[x]);
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==fath) continue;
        Dfs(v,x);
        rt[x]=Merge(rt[x],rt[v],1,n+1);
    }
    for (auto it : q[x]){
        ans[it.ord]=Query(rt[x],1,n+1,it.val);
        // printf("%d : Query(%d)\n",x,it.val);
    }
}

int main(){
    //freopen("CF208E.in","r",stdin);
    //freopen("CF208E.out","w",stdout);
    n=read(); logN=(int)(log2(n)+1);
    for (int i=1;i<=n;++i){
        int x=read();
        if (x==0){ isrt[i]=true; continue; }
        addedge(x,i);
        addedge(i,x);
    }
    m=read();
    for (int i=1;i<=n;++i)
        if (isrt[i]) dfs(i,0);
    for (int i=1;i<=m;++i){
        int x=read(),y=read();
        // printf("jump(%d,%d)=%d\n",x,y,jump(x,y));
        int anc=jump(x,y);
        if (anc) q[anc].push_back((Ques){dep[x],i});
    }
    for (int i=1;i<=n;++i)
        if (isrt[i]) Dfs(i,0);
    for (int i=1;i<=m;++i)
        printf("%d ",max(ans[i]-1,0));
    printf("\n");
    bool Ed; cerr<<"MemoryUsed:"<<1.0*(&St-&Ed)/1024/1024<<endl;
    return 0;
}

树剖求 $k$ 级祖先:

namespace TCP{

    int son[N],newid[N],top[N],rev[N],timer=0;

    inline void dfs1(int x){
        son[x]=0;
        for (int i=head[x];i;i=e[i].nxt){
            int v=e[i].vet;
            dfs1(v);
            if (siz[v]>siz[son[x]]) son[x]=v;
        }
    }

    inline void dfs2(int x,int tp){
        top[x]=tp; newid[x]=++timer;
        rev[timer]=x;
        if (son[x]) dfs2(son[x],tp);
        for (int i=head[x];i;i=e[i].nxt){
            int v=e[i].vet;
            if ((v==fa[x]) || (v==son[x])) continue;
            dfs2(v,v);
        }
    }

    inline int jump(int x,int k){
        int len=0;
        while (true){
            if (!x) return x;
            len+=newid[x]-newid[top[x]];
            // printf("x=%d len=%d k=%d return %d\n",x,len,k,rev[newid[top[x]]+(len-k)]);
            if (len>=k) return rev[newid[top[x]]+(len-k)];
            x=fa[top[x]]; ++len;
        }
    }
}

离线 $dfs$ 求 $k$ 级祖先:

namespace k_fath{
    void dfss(int x){
        sta[++top]=x;
        for (int i=Hed[x];i;i=Q[i].nxt){
            int k=Q[i].val,ord=Q[i].ord;
            int anc=(k>=top) ? (0) : (sta[top-k]);
            if (anc) addquery(anc,dep[x],Q[i].ord);
        }
        for (int i=head[x];i;i=e[i].nxt)
            dfss(e[i].vet);
        --top;
    }
}

我们无法选择过去,但我们可以改变未来。