Cowntagion

题意

有一棵 $N$ 个点的树，初始只有 1 号点有 1 头感染牛。

一天只能做下面两种事件之一：

某个农场内感染牛数量翻倍；
一头感染牛沿一条边移动到相邻农场。

问最少多少天后，每个农场都至少有一头感染牛。

思路

先看一个直接按有根树模拟的写法：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:15
 * update_at: 2026-07-11 20:16
 */
// brute.cpp：小数据朴素解，把树根定为 1 后逐点模拟“翻倍再传播”。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
vector<int> g[MAXN];
long long ans;

int need_double_count(int children) {
    int cows = 1;
    int cnt = 0;
    while (cows < children + 1) {
        cows *= 2;
        cnt++;
    }
    return cnt;
}

void dfs(int u, int fa) {
    int children = 0;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v != fa) children++;
    }

    // 先在当前农场翻倍到足够：给每个孩子 1 头，还要自己留下 1 头。
    ans += need_double_count(children);
    ans += children;

    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v != fa) {
            dfs(v, u);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);
    cout << ans << '\n';

    return 0;
}

把树以 1 号点为根。一个点的任务很固定：

它最终要给每个孩子送 1 头感染牛；
送完以后，它自己也要留下至少 1 头感染牛；
所以如果它有 children 个孩子，就至少需要准备 children + 1 头感染牛。

初始到达某个点时，我们只需要考虑它有 1 头感染牛。每次翻倍后数量变成原来的 2 倍，所以需要的翻倍次数是最小的 $t$ ，满足：

2^t \geqslant children+1

然后还要向每个孩子移动一次，所以移动次数就是 children。

例如样例是一颗星形树：

点	孩子数	需要牛数	翻倍次数	移动次数
1	3	4	2	3
2	0	1	0	0
3	0	1	0	0
4	0	1	0	0

总天数为 $2+3=5$ 。

官方解析还给出一个更简洁的实现：不需要真正 DFS 建根树。

对于 1 号点，孩子数就是它的度数；对于其它点，孩子数等于度数减去父亲这条边，也就是：

text

1
2children(1) = degree(1)
children(i) = degree(i) - 1, i != 1

移动事件总数一定是 $N-1$ ，因为每个非 1 号点都必须通过某条边第一次被感染。

所以答案就是：

(N-1)+\sum_i \left\lceil \log_2(children_i+1) \right\rceil

代码里不用真的算浮点对数，直接从 1 开始不断乘 2，直到不少于 children + 1。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:15
 * update_at: 2026-07-11 20:16
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int degree_cnt[MAXN]; // 无根树上的度数

int need_double_count(int children) {
    int cows = 1;
    int cnt = 0;
    while (cows < children + 1) {
        cows *= 2;
        cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        degree_cnt[a]++;
        degree_cnt[b]++;
    }

    long long ans = n - 1; // 每个非 1 号农场都需要一次移动感染。

    for (int i = 1; i <= n; i++) {
        int children = degree_cnt[i];
        if (i != 1) children--;
        if (children > 0) {
            ans += need_double_count(children);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

只需要统计每个点的度数，再枚举所有点。

时间复杂度为 $O(N)$ 。

空间复杂度为 $O(N)$ 。

总结

本题的关键是把传播过程看成一棵从 1 号点向外扩张的有根树。

每条边只需要传播一次；每个点只需要在向孩子传播之前，先翻倍到足够的牛数。这样整题就变成按每个点的孩子数求翻倍次数。

目录

题意

思路

代码

复杂度

总结