Submission #1774669

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    int nxt, to;
};
Edge e[200010];
int head[200010], cnt;
const int LG = 65;
int dp[200010][LG + 2];

void add_edge(int a, int b)
{
    e[++cnt] = (Edge){ head[a], b };
    head[a] = cnt;
}

void dfs(int nod, int tata)
{
    for (int i = head[nod]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == tata)
            continue;
        dfs(v, nod);
        for (int j(0); j <= LG; j++)
            dp[nod][j] += dp[v][j];
    }
    for (int i(LG); i >= 0; i--) {
        if (dp[nod][i] <= 1)
            continue;
        int p(i);
        while (dp[nod][p])
            p++;
        dp[nod][p] = 1;
        for (int j(0); j < p; j++)
            dp[nod][j] = 0;
        return;
    }

    int p(0);
    while (dp[nod][p])
        p++;
    dp[nod][p] = 1;
    for (int i(0); i < p; i++)
        dp[nod][i] = 0;
}

int main()
{
    int n, a, b;
    cin >> n;

    while (--n) {
        cin >> a >> b;
        add_edge(a, b);
        add_edge(b, a);
    }

    dfs(1, 0);

    for (int i(LG); i >= 0; i--) {
        if (dp[1][i]) {
            cout << i;
            return 0;
        }
    }
    assert(false);
    return 0;
}

Submission Info

Judge Result