最优策略解释

1. 理解问题背景

我们有一个由\(N\)个农场组成的网络，农场之间通过\(N - 1\)条道路连接，形成了一棵树状结构（任意两个农场之间有且仅有一条路径）。最初只有农场\(1\)有一头病牛，疾病传播有两种方式：在农场内病牛数量翻倍，或者病牛沿道路移动到相邻农场。

2. 分析最优策略的组成部分

病牛移动策略

• 对于树状结构，要让所有农场都被感染，病牛最终必须从农场\(1\)（根节点）沿着道路移动到每个叶子节点（没有子节点的农场）。因为树中从根到叶子的路径是唯一的，所以至少需要\(N - 1\)次移动才能确保每个农场都有机会被感染（因为除了根节点，其他\(N - 1\)个节点都需要通过移动来获得病牛）。这就是代码中最初将ans初始化为\(N - 1\)的原因。

病牛数量翻倍策略

• 考虑非叶子节点（度数大于\(1\)的节点或根节点）。假设一个非叶子节点有\(k\)个子节点（对于根节点，所有相连节点都是子节点；对于非根非叶子节点，子节点数量比度数少\(1\)，因为有一条边连接到父节点）。
• 为了最快地将病牛传播到这\(k\)个子节点，我们希望在该节点积累足够多的病牛然后再向子节点扩散。积累病牛的最快方式就是利用翻倍操作。
• 例如，如果有\(3\)个子节点，我们至少需要\(2\)次翻倍操作（最初\(1\)头牛，翻倍后\(2\)头牛，再翻倍后\(4\)头牛，这样就可以向\(3\)个子节点各派出\(1\)头牛）。一般来说，要向\(k\)个子节点传播病牛，我们需要计算满足\(2^n\geq k + 1\)的最小\(n\)，这个\(n\)就是在该节点需要的翻倍操作次数。这就是代码中计算log_children的部分。通过这种方式，我们可以在最少的天数内让病牛从该节点传播到所有子节点。

3. 整体最优性

按照上述移动和翻倍策略，我们可以保证以最少的天数让疾病传播到整个农场网络。先通过合理的翻倍操作在各个节点积累足够的病牛，然后通过移动将病牛送到每个农场，这样的组合方式可以使传播过程最快完成，因为我们在每个节点都以最快的方式进行了病牛数量的扩充和传播。所以这种计算方式得到的结果是最优的最少天数。

// 考察数据结构：树
// 解题点：N个节点 N-1 条边，说明该图无环，可以当树处理

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100000

int N;
int d[MAXN];

int main() {
    // 读取农场数量N
    cin >> N;

    int a, b;
    // 读取N - 1条道路的信息，构建树的结构表示农场之间的连接关系
    // 同时计算每个农场的度数（连接的道路数量）
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b;
        a--, b--;  // 将农场编号调整为从0开始（方便后续数组操作）
        d[a]++, d[b]++;
    }

    int ans = N - 1; // 初始化答案为移动事件的数量（最坏情况，每个农场都需要通过移动感染）

    // 遍历每个农场
    for (int i = 0; i < N; i++) {
        // 如果农场不是叶子节点（度数大于1）或者是根节点（编号为0）
        if (d[i] > 1 || i == 0) {
            int children = d[i];
            if (i!= 0) children--;  // 如果不是根节点，要减去连接到父节点的那条边（因为在计算翻倍次数时不需要考虑父节点方向）

            // 计算以当前节点为根的子树中，将感染传播到所有子节点所需的翻倍事件次数
            // 这里通过不断计算2的幂次方来找到大于等于子节点数量 + 1的最小幂次方，即计算ceil(log(children + 1))
            int log_children = 0;
            int pow = 1;
            while (pow < children + 1)
                log_children++, pow *= 2;

            ans += log_children;
        }
    }

    // 输出结果
    cout << ans << '\n';
}