抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

CodeForces 77C Beavermuncher-0xFF

This is a picture without description

pufanyi

题解

发布于：Jan 12, 2019

原题链接

有一棵树，第 ii 个节点上有 kik_i 只海狸。现在，有一只吃海狸的机器 "Beavermuncher-0xFF" 从根节点 ss 出发，每吃一只海狸，它就能够且必须走到与该节点两边的下一个节点并吃掉那个节点上的一只海狸。该机器每到一个节点，一次都只能吃一只海狸。要求最终机器回到根节点。问该机器最多能吃多少只海狸。

先输入节点个数 n(n≤105)n(n\le 10^5)，然后是nn 个整数 kik_i，后面n−1n−1 行描述一棵树，最后一个整数表示根节点ss。

样例一大概是这样一幅图：

题解

不难发现从一个节点出发，没前往它的一棵子树，都要花费 11 的代价（废话）。

回到父亲又要花费 11 的代价。

所以一个显然的贪心策略就是先花费 ki−1k_{i-1} 的代价“游历”各个儿子，然后再返回父亲。

令 dp[i]dp[i] 表示从 ii 节点“游历”儿子后回到父亲最大所能吃掉的海狸数。但有些节点走完所有儿子后海狸数量还是大于 11。我们记录下每个儿子返回父亲后仍留下的海狸数kx[i]kx[i]，当父亲“游历”完所有儿子后，考虑在父亲与儿子之间往返跑，即i→fa[i]→i→⋯i\to fa[i]\to i\to \cdots。但有些节点无法“游历”所有儿子，那么就把儿子的dpdp 值从大到小排序即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cctype>
#include <cstdio>

namespace IO
{
    const int maxl = 23333;
    char buf[maxl], *sss = buf, *ttt = buf;

    inline char gc()
    {
        if(sss == ttt)
        {
            ttt = (sss = buf) + fread(buf, 1, maxl, stdin);
            if(sss == ttt)
                return EOF;
        }
        return *sss++;
    }

    #define dd c = gc()
    template <class T>
    inline bool read(T& x)
    {
        x = 0;
        bool f = false;
        char dd;
        for(; !isdigit(c); dd)
        {
            if(c == '-')
                f = true;
            else if(c == EOF)
                return false;
        }
        for(; isdigit(c); dd)
            x = (x << 1) + (x << 3) + (c ^ 48);
        if(f)
            x = -x;
        return true;
    }
    #undef dd
}

using IO::read;

#include <set>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<LL, int> pii;

const int maxn = 100005;

int n, k[maxn], kx[maxn], rt;
LL dp[maxn];

struct Edge
{
    int to, nxt;
} e[maxn << 1];

int first[maxn];

inline void add_edge(int from, int to)
{
    static int cnt = 0;
    e[++cnt].nxt = first[from];
    first[from] = cnt;
    e[cnt].to = to;
    e[++cnt].nxt = first[to];
    first[to] = cnt;
    e[cnt].to = from;
}

inline void dfs(int now, int fa)
{
    set<pii> st;
    st.clear();
    dp[now] = (now != rt);
    k[now] -= (now != rt); // 直接把去父亲的代价减掉
    for(int i = first[now]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(fa != to)
        {
            dfs(to, now);
            st.insert(make_pair(dp[to], to));
        }
    }
    int tmp = 0; // 儿子节点 kx 的 sum
    int tmpk = k[now];
    set<pii>::reverse_iterator it; // 倒序遍历 set
    for(it = st.rbegin(); tmpk && it != st.rend(); tmpk--, ++it)
    {
        dp[now] += it->first + 1;
        tmp += kx[it->second];
    }
    dp[now] += min(tmpk, tmp) << 1;
    kx[now] = max(tmpk - tmp, 0);
}

int main()
{
    read(n);
    for(int i = 1; i <= n; ++i)
        read(k[i]);
    for(int i = 1, f, t; i < n; ++i)
        read(f), read(t), add_edge(f, t);
    read(rt);
    dfs(rt, 0);
    printf("%lld\n", dp[rt]);
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://pufanyi.github.io/oi-blog/CF77C/

更新于：Jul 2, 2023

CodeForces

DP

贪心

评论