USACO 2020 December Contest Silver Division - Cowntagion

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

It can be observed after checking a few trees that the answer is n - 1 + sum(log(number of children)).

Source code

The source code in C++ can be seen below.

#include <iostream>
using namespace std;

const int nmax = 1e5 + 5;

int ans = 0;

int lg[nmax];
int sz[nmax];

int main() {
    int n;
    cin >> n;
    ans = n - 1;
    int curr = 0, curr_x = 1;
    for(int i = 1; i < n + 5; i ++) {
        if(curr_x < i) {
            curr_x *= 2;
            curr ++;
        }
        lg[i] = curr;
        if(i < n) {
            int a, b;
            cin >> a >> b;
            sz[a] ++;
            sz[b] ++;
        }
    }
    sz[1] ++;
    for(int i = 1; i <= n; i ++) {
        ans += lg[sz[i]];
    }
    cout << ans;
    return 0;
}