CodeForces 77C Beavermuncher-0xFF

原题链接

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

先输入节点个数 $n (n \leq 10^{5})$ ，然后是 $n$ 个整数 $k_{i}$ ，后面 $n - 1$ 行描述一棵树，最后一个整数表示根节点 $s$ 。

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

样例一：节点记为

i(k_i)

，括号内为海狸数量；根节点

s=4

。

题解

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

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

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

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

代码

cpp

#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;
}

题解

代码

Cite this post