P8276 [USACO22OPEN] Hoof and Brain P 题解

· · 题解

USACO 的题都超有意思的。忘了题意的同志们，我们再来回顾一下：

题意

给定 n 个点，m 条边的无重边、自环的有向图。甲乙两人玩游戏，起初在图上 x,y 点处各放一个棋子，甲先选择一个棋子，乙必须将这个棋子沿着边移动，还需保证两个棋子不重合。轮流进行这一过程，若乙不能移动则乙输，若游戏能无限进行则甲输。对 q 组询问 (x,y)，求谁有必胜策略。n,q\le 10^5，m\le 2\times 10^5。

分析

在做完 P 组的 T3 后，发现第一题是 Benq 出的，所以很不可做，所以我们有大把的时间来好好研究这道 T2。所以我们一步步地分析这个题目。下面称题目中的脑 (Brain,B) 为甲，蹄 (Hoof,H) 为乙。

首先，观察样例的询问，为什么 (1,5) 甲会赢呢？因为 5 点没有出边，于是甲选择这个棋子，乙无处可走。所以初步想法是，如果有一个棋子所在的点出发只能走有限步，就一定是甲赢。如何找到这样的点呢？经典的处理办法是建反图跑拓扑排序，在拓扑序里的点就是无法到达环的点，自然只能走有限步。所以在接下来的分析中，可以将这些点删去，从而不妨设所有点出发都能到达环。

题目没有结束，我们注意到样例中还有 (2,4) 甲会赢。甲可以指定 4，此时乙只能移动到 7，然后甲选 7，乙无处可走。也就是说，如果对于一个棋子所在点 u，它想走无限多步必须经过点 v，且另外一个棋子在 v，那么就是甲赢。这个要求感觉有些苛刻...有没有更一般的结论呢？

比如上图例子，如果棋子初始在 (2,4)，那么甲可以先选 2 再选 4，这两个棋子都必须到 3，产生相遇，甲赢。所以说，我们还可以把这个结论加强，若 u_1,u_2 想走无限步都一定会经过一个点 v，那么 (u_1,u_2) 一定是甲赢。形式化地：

定义 v 是 u 的“支配点”，当且仅当 u 走无限多步必须经过 v。也即，在删去 v 后，u 不在任何大小 >1 的强连通分量内。u 也是 u 的支配点。令 F(u) 为 u 的所有支配点构成的集合，称为支配集。对于询问 u_1,u_2，若 F(u_1)\cap F(u_2) 非空，则甲赢。

对于相交为空的情形，事实上乙会获胜，因为每次都可以避免走到另一个棋子的支配点上。所以至此我们已经找到了甲获胜的等价条件：支配集相交非空。

接下来自然就有了 O(n^2+qn) 的算法：每次删掉一个点，看有多少点无法走到环上，就更新这些点的支配集。询问的时候直接暴力判交即可。事实上，后者还可以用 bitset 优化到 O(\dfrac{qn}{w})，可以通过测试点 1-9。

想要获得更加优秀的做法，就不能暴力求出支配集，而是研究支配的特殊性质。这里我们给出两条：

  1. 传递性：v 支配 u，w 支配 v，则 w 支配 u。
  2. 偏序性：v_1,v_2 都支配 u，则 v_1,v_2 之间也有支配关系。

根据支配点的定义，容易证明以上两条。其中第二条给了我们启发：既然 v_1,v_2 有共同支配的点，那么它们之间也会互相支配，也就是说，u,v_1,v_2 两两有共同支配点。那么...如果将支配关系看作无向图的话，是不是连通块内的任两点都有共同支配点呢？

回顾 NOI2021 庆典。发现那道题对图的限制和第二条很相似，最后的结论是在缩强连通分量之后图为一棵树。强连通分量内的任两点自然有共同支配点；在树上的两点，因为它们共同指向祖先，那么它们也会有共同支配点——祖先！所以至此我们发现，若将支配的关系看作无向，那么连通分支里的任两点的支配集相交非空。

为什么这一结论十分重要？因为它让这道题变得可做：只需要找到不超过 n-1 个支配关系，就能找到所有的连通分支，进而可以用并查集快速地处理询问！

那么如何找到这些支配关系呢？容易想到的是，若出度 \deg u=1，设 u 连向 v，则 v 一定支配 u。那再想，既然 u,v 在支配关系图中同属一个连通块，那是否能在原图里把它们合并呢？事实上可以，因为但凡经过 u 的点一定会下一步经过 v，故将他们合并起来并无大碍。合并时，注意 u,v 缩成的点 u' 可能存在自环。删去重边后，可能会出现新的 u_0 满足 \deg u_0=1，就接着缩点就好了。为了快速地维护缩点的过程，我们可以回顾 WC2021 括号路径 这一题，用线段树合并/启发式合并解决。实现的好可以 O(n\log n)，不过两个 \log 也问题不大。

当然在缩点后，虽然所有点的出度都 \ge 2 了，但仍然不知道是否找全了支配关系。这时惊奇地发现：当前求出的连通分支就是正确的！

引理：若图中每个点的出度 \ge 2，则不存在任何不相同两点的支配关系。
证明：每次从 u 都可找到不经过点 v 的路径，故对任意 u\not=v，v 都不支配 u。证毕。

至此我们解决了这道题。或许你在担心实现起来是不是非常麻烦，或是在后悔赛时没有想到正解...不过没关系，USACO 算什么 无论何时，只要领悟了这道题的精髓，从每道题里学到新知识，为什么不值得高兴呢？:)

Talk is cheap, show you the code... 提前声明，代码太丑，仅供参考~

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,q;
struct Edge{
    int u,v;
    int nxt;
}edge[N<<1];
int head[N],tot=0;
int ind[N],outd[N];
bool ok[N];
int fa[2][N];
int rt[2][N];
struct Tree{
    int siz;
    int ch[2];
}t[N<<6];
int ttot=0,was[N<<5],wastot=0;
bool have[N];
queue<int> tq;
string ans;
inline void add_edge(int u,int v){
    tot++;
    edge[tot]=(Edge){u,v,head[u]};
    head[u]=tot;
    ind[v]++,outd[u]++;
}
#define lson t[id].ch[0]
#define rson t[id].ch[1]
inline void pushup(int id){
    t[id].siz=t[lson].siz+t[rson].siz;
}
inline int NewNode(){ // 加了空间回收，不然会 MLE
    if(wastot){
        return was[wastot--];
    }
    return (++ttot);
}
inline void addwas(int id){
    if(wastot>=(N<<5)) return ;
    t[id].siz=t[id].ch[0]=t[id].ch[1]=0;
    was[++wastot]=id;
}
void Add(int &id,int L,int R,int k,bool del){
    if(!id) id=NewNode();
    if(L==R){
        t[id].siz=del;
        if(!del) addwas(id),id=0;
        return ;
    }
    int mid=(L+R)>>1;
    if(k<=mid) Add(lson,L,mid,k,del);
    else Add(rson,mid+1,R,k,del);
    pushup(id);
    if(!t[id].siz) addwas(id),id=0;
}
bool Have(int id,int L,int R,int k){
    if(!id) return false;
    if(L==R&&t[id].siz) return true;
    int mid=(L+R)>>1;
    return (k<=mid)?Have(lson,L,mid,k):Have(rson,mid+1,R,k);
}
int Findson(int id,int L,int R){
    if(L==R) return L;
    int mid=(L+R)>>1;
    if(t[lson].siz) return Findson(lson,L,mid);
    else return Findson(rson,mid+1,R);
}
inline int find(int k,int x){
    if(x==fa[k][x]) return x;
    return fa[k][x]=find(k,fa[k][x]);
}
int shanx,shany;
void Merge(int &x,int y,int L,int R){
    if(!y) return ;
    if(!x) x=y;
    if(L==R){
        if(t[y].siz){
            Add(rt[1][shanx],1,n,L,1);
            int pp=find(0,L);
            Add(rt[0][pp],1,n,shany,0),Add(rt[0][pp],1,n,shanx,1);
            if(t[rt[0][pp]].siz==1 && !have[pp]) tq.push(pp);
        }
        t[x].siz=(t[x].siz|t[y].siz);
        return ;
    }
    int mid=(L+R)>>1;
    Merge(t[x].ch[0],t[y].ch[0],L,mid);
    Merge(t[x].ch[1],t[y].ch[1],mid+1,R);
    pushup(x);
}
inline int makemerge(int k,int x,int y){ // y merge in x
    int fx=find(k,x),fy=find(k,y);
    if(fx!=fy) fa[k][fy]=fx;
}
void Topo(){
    for(int i=1;i<=n;i++){
        if(!ind[i]) tq.push(i),ok[i]=true;
    }
    while(!tq.empty()){
        int tp=tq.front();tq.pop();
        for(int i=head[tp];i;i=edge[i].nxt){
            int v=edge[i].v;
            if(!(--ind[v])) tq.push(v),ok[v]=true;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(v,u);
    }
    Topo();
    for(int i=1;i<=m;i++){
        int u=edge[i].u,v=edge[i].v;
        if(ok[u] || ok[v]) continue;
        Add(rt[0][v],1,n,u,1);
        Add(rt[1][u],1,n,v,1);
    }
    for(int i=1;i<=n;i++){
        fa[0][i]=fa[1][i]=i;
        if(ok[i]) continue;
        if(t[rt[0][i]].siz==1) tq.push(i);
    }
    while(!tq.empty()){
        int tp=tq.front();tq.pop();
        int now=find(0,tp),now1=find(1,tp);
        if(t[rt[0][now]].siz!=1 || have[now]) continue;
        int to=Findson(rt[0][now],1,n),nowto=find(0,to),nowto1=find(1,to);
        makemerge(0,to,tp);
        if(Have(rt[0][nowto],1,n,now1)) Add(rt[0][nowto],1,n,now1,0),Add(rt[1][now1],1,n,nowto,0),have[nowto]=true;
        Add(rt[1][nowto1],1,n,now,0);
        if(t[rt[1][now1]].siz < t[rt[1][nowto1]].siz){
            makemerge(1,nowto1,now1);
            shanx=nowto1,shany=now1,Merge(rt[1][nowto1],rt[1][now1],1,n);
        }
        else{
            makemerge(1,now1,nowto1);
            shanx=now1,shany=nowto1,Merge(rt[1][now1],rt[1][nowto1],1,n);
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(ok[u] || ok[v]){
            ans+='B';
            continue; 
        }
        int fu=find(0,u),fv=find(0,v);
        if(fu==fv) ans+='B';
        else ans+='H';
    }
    cout<<ans<<endl;
}