Submission #1294871

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <set>
#include <cstdio>
#include <complex>
#include <cstring>
 
using namespace std;
 
const int N = 100000 + 5;
 
int n;
vector<int> adj[N];
set<int> s[N];
 
set<int>& dfs(int u, int f)
{
    set<int> &have = s[u];
    int a = -1;
 
    for(auto v: adj[u]) {
        if (v == f) continue;
        set<int> &f = dfs(v, u);
        if (have.size() < f.size()) {
            have.swap(f);
        }
        for(auto e: f) {
            if (have.count(e)) {
                a = max(a, e);
            } else {
                have.insert(e);
            }
        }
    }
 
    int b = a + 1;
    for( ; have.count(b); b++);
//    for( ; have.size() && *have.begin() <= b; have.erase(have.begin()));
    have.insert(b);
    return s[u];
}
 
void solve()
{
    cin >> n;
    for(int i = 0; i < n - 1; ++ i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    set<int> ret = dfs(0, -1);
    int ans = *ret.rbegin();
    cout << ans << endl;
}
 
int main()
{
    solve();
    return 0;
}

Submission Info

Judge Result