题解：P5157 [USACO18DEC] The Cow Gathering P

· · 题解

没意思的题目。

题意是，给出一棵 n 个节点的树，让你按某种顺序删点直到只剩一个点，使得除最后一次删点之外的过程中，每一次删点之后都不能出现孤点。

此外有 m 个限制，形如 (u,v)，意思是 u 必须在 v 前面被删除。

现在要你求出最后剩下的那一个点可以是哪些点。

要刻画两个东西：不能删出孤点、顺序满足给定的 m 条限制。

后者单独看是一个拓扑排序判环问题，前者需要琢磨一下。

假设当前钦定最后剩下的点为 u，令其为根，那么对于 v，不难发现一定满足 v 在 fa_v 前删除。

考虑证明，如果 fa_v=u 那么是肯定的；反之先删除 fa_v 会让 v 和 u 位于两个连通块，v 一定要在 u 前删除，那么一定要先删除 v 的连通块，此时一定会出现孤点的情况。

刻画先后顺序可以连有向边，以 u 为根情况下，将 v 向 fa_v 连有向边，并将那 m 条限制的形成的有向边也加过来，形成一张有向图，判定只需要拓扑排序判断，这样就有了 O(n(n+m)) 的做法，需要优化。

下称额外的 m 条限制形成的有向边为“非树边”。

考虑如果无解，形成的环长什么样子。

一种是纯由非树边构成的环，这个可以提前判掉，如果有环说明肯定没有合法删除顺序，意味着没有一个点有解。

另一种是由一条非树边加若干条树边形成的环，为什么只需要一条？画图发现，如果有多条非树边形成的环，必然能剖出只有一条非树边形成的环。

继续画图，发现对于非树边 (u,v)，如果 u 是 v 的祖先，那么只有 u 的一个儿子 x，满足 x 子树内有 v，除了 x 子树之外的点均无解，也就是说，有解的点只能在 x 子树内，找 x 可以用树上倍增实现。

如果 u 不是 v 的祖先，那么 u 子树内的点均无解。

用 dfs 序转将子树限制化为区间限制，可以通过差分来标记第二个情况，第一个情况，记录所有合法子树的 dfs 序区间交即可。

如果一个点有解，需要满足，非树边不成环、没有被第一种情况标记、dfs 序位于第二种情况交出的区间内。

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

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()

#define N 102510
// #define int long long

int n,m,siz[N],dfn[N],fa[19][N],d[N],num;
int dl[N];
vector<int>e[N];

inline void dfs(int k,int pa){
    dfn[k]=++num;
    siz[k]=1;

    d[k]=d[pa]+1;
    fa[0][k]=pa;
    rep(i,1,18){
        fa[i][k]=fa[i-1][fa[i-1][k]];
    }

    for(int x:e[k]){
        if(x==pa){
            continue;
        }
        dfs(x,k);
        siz[k]+=siz[x];
    }
}

namespace topo{
    vector<int>e[N];
    int d[N];

    inline bool chk(){
        queue<int>q;
        rep(i,1,n){
            if(!d[i]){
                q.push(i);
            }
        }

        while(!q.empty()){
            int u=q.front();
            q.pop();

            for(int x:e[u]){
                d[x]--;
                if(!d[x]){
                    q.push(x);
                }
            }
        }

        return *max_element(d+1,d+1+n)==0;
    }
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;

    rep(i,1,n-1){
        int u,v;
        cin>>u>>v;
        e[u].pb(v);
        e[v].pb(u);
    }

    dfs(1,0);

    int L=1,R=n;

    rep(i,1,m){
        int u,v;
        cin>>u>>v;
        topo::e[u].pb(v);
        topo::d[v]++;

        if(dfn[v]>=dfn[u]&&dfn[v]<=dfn[u]+siz[u]-1){
            per(j,0,18){
                if(d[fa[j][v]]>d[u]){
                    v=fa[j][v];
                }
            }

            L=max(L,dfn[v]);
            R=min(R,dfn[v]+siz[v]-1);
        }
        else{
            dl[dfn[u]]++;
            dl[dfn[u]+siz[u]]--;
        }
    }

    bool dag=topo::chk();

    rep(i,1,n){
        dl[i]+=dl[i-1];
    }

    rep(i,1,n){
        if(dag&&!dl[dfn[i]]&&dfn[i]>=L&&dfn[i]<=R){
            cout<<"1\n";
        }
        else{
            cout<<"0\n";
        }
    }

    return 0;
}