题解 P5157 【[USACO18DEC]The Cow Gathering】

Bartholomew · 2019-02-02 20:23:47 · 题解

简化题意

简化为给定一棵大小为n的树, 有m个限制

• 限制(u,v) 表示u必须在v前删除

问每次删除一个叶子节点, 可能最后留下的点的集合

分析

nice problem

不难发现: 如果没有限制, 那么所有的点都可行...

首先, 我们可以贪心先找出一个可行点, 解决方法如下

每次寻找一个没有限制条件的叶子节点删去 重复上述操作, 最后的节点即为可行答案之一 若不成功, 则视为无解

Prove

• 如果本身数据无解, 那么自然上述方法找不到一个合法的删点序列

• 同样的, 如果不存在一个合法的删点序列, 那么必定意味着存在一个连续的子树: 子树中的任意一个点都被其他点的约束限制着, 类似于形成了环. 那么就不会存在任意一个序列可以打破这种局面了.

于是证明了该方法是可以找出合法点以及判断无解的!

sol

先提供一个O(n^2)的做法:

• 每次判断一个点是否可行, 只要将它提为root,并将所有边记为子节点指向父节点
• 若不存在环便是可行点, 否则非法!

那么会发现一个trick:

• 若存在限制(u,v)那么以v为根的u的子树(包括u)都不可行

这样就可以搞事情了

我们既然已经找出了一个可行解(记为rt)

• 以rt为根可以发现任意一个限制(a,b)中, a的子树一定是不可行的(证明略)

• 那么标记完不可行点之后剩下的点都是可行的!

  Prove 利用数学归纳: 只要证明与一个可行点相邻的且未被标记过的点同样合法即可!

  设该可行点为s, 转为root, 那么t为其子节点 如果关于s的合法删除序列为\{a_n\} s.t. a_n=s,a_x=t (x\in Z) 那么我们直接将a_x提至序列的a_n之后, 该序列同样合法

  因为没有t必须在某一点前删除的限制, 否则t已经在之前被标记为非法!

  且t的子树可以按序删除(不然s不会为合法点),以及s的非t子树部分同样可以删除,依旧不会被t所干扰

那么可以发现所有的可行解必定都是一起的, 一遍dfs即可...

复杂度: O(n)

Code

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

namespace {
    template <typename T> inline void read(T &x) {
        x = 0; T f = 1; char c = getchar();
        for(; !isdigit(c); c = getchar())
            if(c == '-') f = -1;
        for(;  isdigit(c); c = getchar())
            x = (x << 3) + (x << 1) + (c ^ 48);
        x *= f;
    }
}

const int N = 1E5 + 50;

int n, m, rt, d[N], vis[N], ans[N];
vector<int> g[N], l[N];
queue<int> que;

int cnt;
int solve(int cnt = 0) {
    for(; !que.empty(); ) {
        int u = que.front(); que.pop();
        ++ cnt;
        if(d[u] != 1) {
            if(d[u] < 1) return u;
            for(int i = 1; i <= n; ++i) printf("0\n");
            exit(0);
        } 
        for(auto v : g[u]) {
            -- d[v]; ++ cnt;
            if(d[v] == 1) que.push(v);
        }
        for(auto v : l[u]) {
            -- d[v]; ++ cnt;
            if(d[v] == 1) que.push(v);
        }
    }
    if(cnt != n) {
        for(int i = 1; i <= n; ++i) printf("0\n"); 
        exit(0);
    }
}
void dfs(int u, int fa = -1) {
    ans[u] = 1;
    for(auto v : g[u]) 
        if(v != fa && !vis[v]) 
            dfs(v, u);
}
int main() {
    read(n), read(m);
    for(int u, v, i = 1; i < n; ++i) {
        read(u), read(v);
        g[u].push_back(v), g[v].push_back(u); 
        ++ d[u], ++ d[v];
    }
    for(int a, b, i = 1; i <= m; ++i) {
        read(a), read(b);
        l[a].push_back(b);
        ++ d[b];
        vis[a] = true;
    }
    for(int i = 1; i <= n; ++i) 
        if(d[i] == 1) que.push(i);
    rt = solve();
    dfs(rt);
    for(int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}