Submission #1772822

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair

int read()
{
    int v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

const int N = 101000;

int n, f[N][31];

struct Edge
{
    int nxt, to;
} eg[N << 1];
int head[N], en;

void setEdge(int u, int v)
{
    eg[++en] = (Edge) {head[u], v};
    head[u] = en;
}

void dfs(int u, int fa)
{
    for (int e = head[u]; e; e = eg[e].nxt)
    {
        int v = eg[e].to;
        if (v == fa) continue;
        dfs(v, u);
        for (int i = 0; i <= 30; i++)
            f[u][i] += f[v][i];
    }
    for (int i = 0; i <= 30; i++)
        if (f[u][i] == 0)
        {
            f[u][i] = 1;
            for (int j = 0; j < i; j++)
                f[u][j] = 0;
            for (int j = i + 1; j <= 30; j++)
                if (f[u][j]) f[u][j] = 1;
            break;
        }
}

int main()
{
    n = read();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        setEdge(u, v);
        setEdge(v, u);
    }
    dfs(1, 0);
    for (int i = 30; i >= 0; i--)
        if (f[1][i])
        {
            printf("%d\n", i);
            return 0;
        }
}

Submission Info

Judge Result