思路

我们可以想到，每次在一个点翻倍到足够把子节点都覆盖的时候传播到子节点，至于传播后多余的有两种情况，一种情况是传输到子节点，使得子节点的翻倍数量减少。但是实际发现这样是不现实的，因为传输需要用的时间比翻倍需要用的时间更多（可以感性的理解一下，因为具体的证明我也不会）

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector <int> e[100005];
bool cmp(int x, int y) {
    return e[x].size() > e[y].size();
}
int p[1000005];
int cal(int x) {
    if (x == 0) return 0;
    int pos = lower_bound(p + 1, p + 60 + 1, x) - p;
    return pos;
}
int ans = 0;
void dfs(int nw, int fa, int res) {
    int days = cal(e[nw].size() - 1);
    if (p[days] == e[nw].size() - 1) days ++;
//  if (nw == 1) cout << nw << " " << e[nw].size() << " " << days << " " << p[days] << "\n";
    ans += days;
    for (auto x : e[nw]) {
        if (x == fa) continue;
        ans ++;
        dfs(x, nw, res + p[days] - e[nw].size());
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("5.in", "r", stdin);
    cin >> n;
    p[0] = 1;
    for (int i = 1; i <= 60; i ++) {
        p[i] = p[i - 1] * 2;
    }
    e[1].push_back(0);
    for (int i = 1; i < n; i ++) {
        int x, y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i = 1; i <= n; i ++) sort(e[i].begin(), e[i].end(), cmp);
    dfs(1, 0, 0);
    cout << ans;
    return 0;
}