Chlience

【题解】LUOGU [USACO18DEC]The Cow Gathering
Problem给定一棵树,每次可以删去一个叶子节点,在满足一些先后关系的顺序下,问每个点能否作为被删的最后一个点T...
扫描右侧二维码阅读全文
28
2019/01

【题解】LUOGU [USACO18DEC]The Cow Gathering

Problem

给定一棵树,每次可以删去一个叶子节点,在满足一些先后关系的顺序下,问每个点能否作为被删的最后一个点

Thought

假设有一对先后关系 $(a,b)$ ,假设 $a$ 先 $b$ 后,那么以 $b$ 为根 $a$ 子树中的节点必然要优先删除,也就是说不可能最后离开

如何维护每次能够选的位置?

只需要找到 $b$ 在 $a$ 的子树/父亲的方向
如果 $b$ 是 $a$ 的祖先,那么在根节点打上 $+1$ 标记,在 $a$ 打上 $-1$ 标记
如果 $a$ 是 $b$ 的祖先,那么在 $a$ 的位置打上 $+1$ 标记

$+1$ 标记不影响当前点, $-1$ 标记影响当前点

那么最后标记个数等于先后关系对数的点即可以选择的点

或者也可以维护不能选的位置
如果 $b$ 是 $a$ 的祖先,那么 $a$ 的子树不能选,打上标记
如果 $a$ 是 $b$ 的祖先,除了 $b$ 的子树外都不能选,打上标记

最后没有被标记的点就是即可以选择的点

然后判断能否成立可以用拓扑

既然说到拓扑,今年下半年 中美合拍的西游记即将正式开机
其实还有个很妙的方法来做这道题

直接拓扑,如果最后只剩下一个点,那么说明这个图是合法的
显然,最后一个点是可以作为最后一个点的(绕得很

然后,最后一个点能够直接到达的所有点也是能选的
当且仅当遇到一个需要先选的节点,那么不能继续向该方向扩展

为啥呢?

显然最后一个点肯定是不在该点的子树中的,那么该点的后选点肯定在最后一个点的方向上,也就是说不影响最后一个点扩展出来的答案

所以最后直接一个 $BFS/DFS$ 就行了

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n, m;
struct Edge {
    int t, n;
};
int head[N], tot;
Edge e[N << 2];
int in[N];
int topo[N], top;
bool use[N];
bool vis[N];
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
void topology() {
    queue <int> q;
    for(int i = 1; i <= n; ++ i)
        if(in[i] == 1)
            q.push(i);
    while(!q.empty()) {
        int now = q.front(); q.pop();
        topo[++ top] = now;
        for(int i = head[now]; i; i = e[i].n) {
            -- in[e[i].t];
            if(in[e[i].t] == 1)
                q.push(e[i].t);
        }
    }
}
void dfs(int x) {
    vis[x] = use[x] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        if(vis[e[i].t] || use[e[i].t]) continue;
        dfs(e[i].t);
    }
}
int main() {
    n = read(); m = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        addedge(u, v); addedge(v, u);
        ++ in[u]; ++ in[v];
    }
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        ++ in[v];
        vis[u] = 1;
    }
    topology();
    if(top < n)
        for(int i = 1; i <= n; ++ i)
            puts("0");
    else {
        dfs(topo[top]);
        for(int i = 1; i <= n; ++ i)
            printf("%d\n", use[i]);
    }
    return 0;
}
Last modification:January 28th, 2019 at 08:42 am

Leave a Comment