题解 P4183 【[USACO18JAN]Cow at Large P】

dsidsi · 2019-01-04 14:44:25 · 题解

来讲一个非常奇怪的乱搞

首先把所有叶子节点丢进队列BFS。得到每个节点距离最近叶子节点的距离。

设奶牛在a点，然后考虑一个节点b被子树里的叶子保护(即奶牛一旦走到这个节点就会被捕捉)的条件是

然后就可以写一个O(n^2)的贪心了，只要当前点能被子树的节点保护，则++ans。因为一棵子树肯定越早被保护越好。

显然是无法通过此题的。

可以发现，对于一条链，在链的顶端被保护和在链的底端保护的答案不变。所以只需要把一条链缩成一条边，然后贪心即可。

复杂度 O(玄学)，实际运行速度目前Rank1。吊打点分治

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

const int maxn = 70005;

int n, ans;

struct edge
{
    int to, next;
    int To, fa, w;
} e[maxn * 2];
int h[maxn], d[maxn], tot;

queue<int> q;
int f[maxn], eu, ev, ew;

inline int gi()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int sum = 0;
    while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

inline void add(int u, int v)
{
    e[++tot] = (edge) {v, h[u]}; h[u] = tot; ++d[v];
    e[++tot] = (edge) {u, h[v]}; h[v] = tot; ++d[u];
}

void bfs()
{
    for (int i = 1; i <= n; ++i)
        if (d[i] == 1) f[i] = 0, q.push(i);
        else f[i] = -1;
    int u;
    while (!q.empty()) {
        u = q.front(); q.pop();
        for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
            if (f[v] == -1) {
                f[v] = f[u] + 1;
                q.push(v);
            }
    }
}

void dfs1(int u, int fa, int dep)
{
    if (fa && d[u] != 2) return eu = u, ev = fa, ew = dep, void();
    for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
        if (v != fa) {
            dfs1(v, u, dep + 1);
            e[i].To = eu; e[i].fa = ev; e[i].w = ew - dep;
        }
}

void dfs2(int u, int fa, int dep)
{
    if (f[u] <= dep) return ++ans, void();
    for (int i = h[u]; i; i = e[i].next)
        if (e[i].to != fa) dfs2(e[i].To, e[i].fa, dep + e[i].w);
}

int main()
{
    n = gi();
    for (int i = 1; i < n; ++i) add(gi(), gi());

    bfs();

    tot = 0;
    for (int i = 1; i <= n; ++i)
        if (d[i] != 2) dfs1(i, 0, 0);

    for (int i = 1; i <= n; ++i) {
        ans = 0; dfs2(i, 0, 0);
        printf("%d\n", ans);
    }

    return 0;
}