专栏文章

题解：P5157 [USACO18DEC] The Cow Gathering P

LLucyna_Kushinada
P5157题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5rlgn
此快照首次捕获于
2025/12/01 21:01
3 个月前
此快照最后确认于
2025/12/01 21:01
3 个月前
查看原文
没意思的题目。
题意是，给出一棵 nn 个节点的树，让你按某种顺序删点直到只剩一个点，使得除最后一次删点之外的过程中，每一次删点之后都不能出现孤点。
此外有 mm 个限制，形如 (u,v)(u,v)，意思是 uu 必须在 vv 前面被删除。
现在要你求出最后剩下的那一个点可以是哪些点。
要刻画两个东西：不能删出孤点、顺序满足给定的 mm 条限制。
后者单独看是一个拓扑排序判环问题，前者需要琢磨一下。
假设当前钦定最后剩下的点为 uu，令其为根，那么对于 vv，不难发现一定满足 vv 在 favfa_v 前删除。
考虑证明，如果 fav=ufa_v=u 那么是肯定的；反之先删除 favfa_v 会让 vv 和 uu 位于两个连通块，vv 一定要在 uu 前删除，那么一定要先删除 vv 的连通块，此时一定会出现孤点的情况。
刻画先后顺序可以连有向边，以 uu 为根情况下，将 vv 向 favfa_v 连有向边，并将那 mm 条限制的形成的有向边也加过来，形成一张有向图，判定只需要拓扑排序判断，这样就有了 O(n(n+m))O(n(n+m)) 的做法，需要优化。
下称额外的 mm 条限制形成的有向边为“非树边”。
考虑如果无解，形成的环长什么样子。
一种是纯由非树边构成的环，这个可以提前判掉，如果有环说明肯定没有合法删除顺序，意味着没有一个点有解。
另一种是由一条非树边加若干条树边形成的环，为什么只需要一条？画图发现，如果有多条非树边形成的环，必然能剖出只有一条非树边形成的环。
继续画图，发现对于非树边 (u,v)(u,v)，如果 uu 是 vv 的祖先，那么只有 uu 的一个儿子 xx，满足 xx 子树内有 vv，除了 xx 子树之外的点均无解，也就是说，有解的点只能在 xx 子树内，找 xx 可以用树上倍增实现。
如果 uu 不是 vv 的祖先，那么 uu 子树内的点均无解。
用 dfs 序转将子树限制化为区间限制，可以通过差分来标记第二个情况，第一个情况，记录所有合法子树的 dfs 序区间交即可。
如果一个点有解，需要满足，非树边不成环、没有被第一种情况标记、dfs 序位于第二种情况交出的区间内。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...