[CF466E] Information Graph

Description

公司中有 (n) 名员工，开始时员工之间没有任何联系，接下来会依次发生 (m) 条事件，类型有三种。

1. (y) 成了 (x) 的上司
2. (x) 得到了一份文件，(x) 把文件传给了他的上司，他的上司又会传给上司的上司，直到某人没有上司，此时文件被销毁
3. 询问 (x) 是否看过第 (i) 份文件

Solution

考虑离线处理，时序扫描，第一轮处理 1,2 操作，第二轮处理询问

对于操作 1，在并查集中合并 (x,y)（顺序！），在森林中加边

对于操作 2，我们将这份文件记录下来，其信息为 (x) 和它在并查集中的根

时序扫描过程中，设第 (i) 份文件涉及的两个点是 (p_i,q_i)，我们只需要检查 (x) 是否在 (p,q) 构成的链上即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;
const int M = 20;

int n,m,t1,t2,t3;

struct Forest
{
    int fa[N][M],dep[N],vis[N],deg[N];
    vector <int> g[N];

    void make(int p,int q)
    {
        g[q].push_back(p);
        deg[p]++;
    }

    void dfs(int p)
    {
        vis[p]=1;
        for(int q:g[p])
        {
            dep[q]=dep[p]+1;
            fa[q][0]=p;
            dfs(q);
        }
    }

    void presolve()
    {
        for(int i=1;i<=n;i++)
        {
            if(deg[i]==0)
            {
                dep[i]=1;
                dfs(i);
            }
        }
        for(int j=1;j<M;j++)
        {
            for(int i=1;i<=n;i++)
            {
                fa[i][j]=fa[fa[i][j-1]][j-1];
            }
        }
    }

    bool check_relation(int p,int q)
    {
        for(int i=M-1;i>=0;--i)
        {
            if(dep[fa[p][i]]>=dep[q]) p=fa[p][i];
        }
        return p==q;
    }

    bool query(int p,int q,int v)
    {
        return check_relation(p,v) && check_relation(v,q);
    }
} forest;

struct Dsu
{
    int fa[N];

    void init()
    {
        for(int i=1;i<=n;i++) fa[i]=i;
    }

    int find(int p)
    {
        return fa[p]==p ? p : fa[p]=find(fa[p]);
    }

    void merge(int p,int q)
    {
        p=find(p);
        q=find(q);
        if(p!=q) fa[p]=q;
    }
} dsu;

struct Document
{
    int p,q;
} doc[N];

struct Request
{
    int x,i;
} req[N];

int nreq;

int ndoc;

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;

    dsu.init();

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

        if(t1==1)
        {
            cin>>t2>>t3;
            forest.make(t2,t3);
            dsu.merge(t2,t3);
        }
        else if(t1==2)
        {
            cin>>t2;
            doc[++ndoc]={t2,dsu.find(t2)};
        }
        else if(t1==3)
        {
            cin>>t2>>t3;
            req[++nreq]={t2,t3};
            if(dsu.find(t2) != dsu.find(doc[t3].p)) req[nreq].x=-1;
        }
    }

    forest.presolve();

    for(int u=1;u<=nreq;u++)
    {
        int x=req[u].x, i=req[u].i;
        if(x>0)
        {
            if(forest.query(doc[i].p,doc[i].q,x))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
}