「USACO18DEC Platinum C」 The Cow Gathering

· · 题解

USACO 2018 DEC Platinum The Cow Gathering

题意：给定树和一些树上有向边，每次删去叶子，询问每个结点能否最后一个删去

题解：

判断一个点能否最后一个删，就把它提做根，然后把所有儿子都往上指

加入一条边 (u,v) 可以发现以v为根时u的子树都没法最后删

根据这个性质，每次加边钦定一些点答案就是0

怎样快速找到u在以v为根的树中的子树？用类似「遥远的国度」那题的方法，直接以1号点为根建树，然后这时换根只需要分类讨论一下：如果v在u子树外，不用动；如果v在子树内，那找到v在u的哪个儿子的子树里，除了这个子树其他所有结点钦定答案为0。具体实现就找倍增找v的deep[v]-deep[u]-1级祖先（因为如果暴力遍历儿子，复杂度不对），覆盖就dfs序差分一下

其实此时的做法还是有一些问题的，USACO比赛时很多选手就这样写的，但后来出题人中途加数据把他们叉掉了

因此需要判下图是否无解

我们把已经确定答案为0的结点确定边的方向，然后加上树上有向边判环。

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

int n, m, dfn[N], idx[N], sz[N];
int fa[N][20], d[N];
vector<int> G[N], g[N];
bool ans[N];

void dfs(int u, int f = 0) {
    fa[u][0] = f; d[u] = d[f] + 1;
    for(int i = 1; i < 20; i ++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    dfn[u] = ++ dfn[0]; idx[dfn[u]] = u; sz[u] = 1;
    for(int i = 0; i < G[u].size(); i ++) if(G[u][i] != f)
        dfs(G[u][i], u), sz[u] += sz[G[u][i]];
}

int c[N];

inline void cover(int l, int r) {
    if(l <= r) c[l] ++, c[r + 1] --;
}

void kthfa(int & u, int k) {
    if(k > 0) for(int i = 0; i < 20; i ++) 
        if(k >> i & 1) u = fa[u][i];
}

bool vis[N];
void fixdir(int u, int f) {
    for(int & v : G[u]) if(v != f) {
        if(!vis[v]) {
            g[v].push_back(u);
            vis[v] = 1; fixdir(v, u);
        }
    }
}

bool vis2[N], ins[N];
bool cir(int u) {
    if(ins[u]) return 1;
    if(vis2[u]) return 0;
    vis2[u] = ins[u] = 1;
    for(const int & v : g[u]) 
        if(cir(v)) return 1;
    return ins[u] = 0;
}

int main() {
    scanf("%d%d", &n, &m);
    int u, v;
    for(int i = 1; i < n; i ++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1);
    for(int i = 1; i <= m; i ++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        int l = dfn[u], r = l + sz[u] - 1;
        if(dfn[v] < l || dfn[v] > r) {
            cover(l, r), fixdir(u, fa[u][0]);
        } else {
            kthfa(v, d[v] - d[u] - 1);
            int l2 = dfn[v], r2 = l2 + sz[v] - 1;
            cover(1, l2 - 1), cover(r2 + 1, n);
            for(const int & j : G[v]) if(!vis[j]) {
                if(dfn[j] < l2 || dfn[j] > r2) {
                    vis[j] = 1;
                    fixdir(j, v);
                }
            }
        }
    }
    bool tag = true;
    for(int i = 1; i <= n; i ++) if(!vis2[i])
        if(cir(i)) tag = false, i = n;

    if(!tag) {
        for(int i = 1; i <= n; i ++) puts("0");
        return 0;
    }

    int val = 0;
    for(int i = 1; i <= n; i ++)
        val += c[i], ans[idx[i]] = (val > 0) ? 0 : 1;
    for(int i = 1; i <= n; i ++)
        printf("%d\n", ans[i]);
    return 0;
}