CF466E Information Graph 题解

题目链接

Luogu

Codeforces

题意简述

某公司中有 \(n\) 名员工。为方便起见,将这些员工从 1 至 \(n\) 编号。起初,员工之间相互独立。接下来,会有以下 \(m\) 次操作:

  1. 员工 \(y\) 成为员工 \(x\) 的上司。保证此前 \(x\) 没有上司

  2. 员工 \(x\) 拿到一份文件并签字,随后交给他的上司。他的上司签字后,再交给更上一级。依此类推,直到文件传递到的那个人没有上司为止。

  3. 询问员工 \(x\) 是否在第 \(i\) 件文件上签过字。文件编号为上一件文件的编号再加 1,第一件文件的编号为 1。如果是,输出 YES,否则输出 NO

解法说明

显然,我们可以将员工之间的关系看作森林,将每个员工看作一个节点,其与上司的关系看作一条边。之所以不是一棵树,是因为在 \(m\) 次操作中,有些人可能并没有被指定上司,所以员工之间的关系很可能并不是一棵树而是森林

通过观察题面可以发现,一个员工在成为另一个员工的上司后,就不会再有更改了。由于在线操作过于麻烦,我们可以考虑离线

具体离线方法如下:

  • 对于操作 1,直接连边即可,不过这里还要在线维护一个并查集

  • 对于操作 2,分别记下第一个和最后一个对文件签字的员工,后者就是前者所在的连通块的根,利用并查集查找;

  • 对于操作 3,分别记下员工编号及文件编号,离线回答

接下来分析如何回答询问。可以发现,如果询问的员工 \(x\) 在 最开始看到文件 \(i\) 的员工与最后看到文件 \(i\) 的员工之间的链上,那么 \(x\) 就看过文件。所以,问题就被转化为了判断 \(x\) 是否在这条链上

考虑如何判断。

\(st\) 为链的起始点,\(ed\) 为截止点,可推得如 \(x\) 在链上,则 \(\text{lca}(x,st) = x\)\(\text{lca}(x,ed) = ed\),维护一个 LCA 即可求解。我这里用的是树剖求 LCA,倍增也可以。

还有一些细节需要注意。由于员工之间的关系是森林而非一棵树,所以我们在预处理树剖时应枚举每个点,如果该点是其所属的连通块的根,就对其进行一次预处理,且回答询问时应首先判断 \(x\)\(st\)\(ed\) 是否在同一连通块内,如果不在直接输出 NO,否则再执行下一步操作。

剩余细节详见下面代码中的注释。

通过代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define mp make_pair
const int N=1e5+10;

namespace IO{
    //快读 
    inline int read(){
        int x=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*f;
    }
    
    //快写 
    inline void write(int x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9){
            write(x/10);
        }
        putchar(x%10+'0');
    }
} 

using namespace IO;

namespace code{
    //链式前向星存图 
    int head[N],tot;
    
    struct node{
        int ver,next;
    }t[N<<1];
    
    void add(int x,int y){
        t[++tot].ver=y,t[tot].next=head[x],head[x]=tot;
    }
    
    //并查集
    int fa[N];
    
    int getfa(int x){
        if(fa[x]==x){
            return x;
        }
        return fa[x]=getfa(fa[x]);
    } 
    
    //树链剖分 
    int fat[N],size[N],son[N],deep[N],top[N];
    
    void dfs1(int x){
        size[x]=1;
        int maxson=-1;
        for(int i=head[x];i;i=t[i].next){
            int y=t[i].ver;
            if(y==fat[x]){
                continue;
            } 
            fat[y]=x;
            deep[y]=deep[x]+1;
            dfs1(y);
            if(size[y]>maxson){
                maxson=size[y];
                son[x]=y;
            }
            size[x]+=size[y];
        }
    }
    
    void dfs2(int x,int from){
        top[x]=from;
        if(!son[x]){
            return;
        }
        dfs2(son[x],from);
        for(int i=head[x];i;i=t[i].next){
            int y=t[i].ver;
            if(y==son[x]||y==fat[x]){
                continue;
            }
            dfs2(y,y);
        }
    }
    
    //求LCA
    int lca(int x,int y){
        while(top[x]!=top[y]){
            if(deep[top[x]]<deep[top[y]]){
                swap(x,y);
            }
            x=fat[top[x]];
        }
        if(deep[x]<deep[y]){
            return x;
        }
        return y;
    }
    
    //主程序 
    int n,m,f_tot,q_tot;
    PII file[N],query[N];
    
    void solve(){
        n=read(),m=read();
        for(int i=1;i<=n;i++){//并查集预处理 
            fa[i]=i;
        }
        for(int i=1;i<=m;i++){//离线处理 
            int op=read();
            if(op==1){
                int x=read(),y=read();
                add(y,x);//单向边 
                fa[x]=getfa(y);//在线维护并查集 
            }else if(op==2){
                int x=read();
                file[++f_tot]=mp(x,getfa(x));
            }else{
                int x=read(),y=read();
                query[++q_tot]=mp(x,y);
            }
        }
        for(int i=1;i<=n;i++){//枚举所有点 
            if(getfa(i)==i){//判断是否为所在连通块的根 
                deep[i]=1;//树剖预处理 
                fat[i]=i;
                dfs1(i);
                dfs2(i,i);
            }
        }
        for(int i=1;i<=q_tot;i++){
            int x=query[i].first,y=query[i].second,st=file[y].first,ed=file[y].second;
            if(getfa(x)!=getfa(st)){//是否在同一个连通块 
                printf("NO\n");
                continue;
            }
            if(lca(x,st)==x&&lca(x,ed)==ed){//判断 
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }
}

using namespace code;

signed main(){
    solve();
    return 0;
}

热门相关:重生全能悍妻:张狂大小姐   隐婚99天:首长,请矜持   我的女友不可能是怪物   99次出墙:老公,情难自禁   天帝龙魂