2019杭电多校第三场 HDU6604 支配树

题意

给出一个DAG，入度为0的点为控制点，现在有两个点要沿边走向控制点，问破坏哪些点可以使其中一个无法到达，求点的个数

题解

支配树模板题，可惜之前没听说过 😦
逆向建图，然后让0号点连接所有控制中心，对于 $a 、 b$ 两点， $a + b - L C A (a, b)$ 就是答案
由于是DAG，建图方式比较简单

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,LL> pp;
namespace IO{ 
    #define BUF_SIZE 100000 
    #define OUT_SIZE 100000 
    bool IOerror=0; 
    inline char nc(){ 
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
        if (p1==pend){ 
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
            if (pend==p1){IOerror=1;return -1;} 
        } return *p1++; 
    } 
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 
    inline void read(int &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); if (IOerror)return; if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if (sign)x=-x; 
    } 
};using namespace IO;
vector<int> a[N],b[N],c[N];
int in[N],p[N],st[N],d[N],cnt,n,m;;

void topsort(){
    int top=1;
    for(int i=1;i<=n;i++) if(!in[i]) a[0].pb(i),b[i].pb(0),in[i]++;
    st[1]=0;
    while(top){
        int x=st[top--]; p[++cnt]=x; 
        for(auto i:a[x]){
            in[i]--;if (!in[i]) st[++top]=i;
        }
    }
}
int f[N][18];

int lca(int x,int y){
    if (d[x]<d[y]) swap(x,y);
    for(int i=17;i>=0;i--) if (d[f[x][i]]>=d[y]) x=f[x][i];
    if (x==y) return x;
    for(int i=17;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

int main()
{
    int T;
    read(T);
    while(T--){
        read(n);read(m);
        for(int i=0;i<=n;i++) a[i].cl(),b[i].cl(),c[i].cl(),in[i]=0;
        while(m--){
            int x,y;
            read(x);read(y);
            a[y].pb(x);b[x].pb(y);in[x]++;
        }
        cnt=0;
        topsort();
        for(int i=2;i<=cnt;i++){
            int x=p[i]; int y=b[x][0];
            for(auto i:b[x]) y=lca(y,i);
            f[x][0]=y; c[y].pb(x); d[x]=d[y]+1; 
            for(int i=1;i<=17;i++) f[x][i]=f[f[x][i-1]][i-1];
        }

        read(m);
        while(m--){
            int x,y;
            read(x);read(y);
            printf("%d\n",d[x]+d[y]-d[lca(x,y)]);
        }
    }
    return 0;
}