UJGOI 2022 Day 3B

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

constexpr long long INF = (long long)1e18;
constexpr int N = (int)3e5 + 111;
constexpr int md = (int)998244353;
constexpr int mdPower = (int)1e9+7 - 1;
constexpr double eps = 1e-7;

typedef __int128 _uint;
typedef long long ll;

mt19937_64 rnd(time(nullptr));

void add(int& a,int b){
    a += b; if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b; while(a < 0) a += md;
}
void add(__int128& a,int b){
    a += b;
}
void sub(__int128& a,int b){
    a -= b;
}

int bpow(int a,int b){
    if(b == 0)
        return 1;
    if(b % 2 == 0){
        int t = bpow(a,b>>1);
        return 1ll*t*t%md;
    }
    return 1ll * a*bpow(a,b-1) % md;
}

int inv(int a){
    return bpow(a,md-2);
}

vector<int> g[N];
int diam[N];
int ans = 0;
multiset<int> st[2];
int mxD[N];

int dfs1(int v,int pr = -1){
    int mx[2],a;
    mx[0] = mx[1] = 0;
    for(auto& to : g[v]){
        if(to == pr)
            continue;
        a = dfs1(to,v)+1;
        diam[v] = max(diam[to],diam[to]);
        if(a > mx[1])
            swap(a,mx[1]);
        if(mx[0] < mx[1])
            swap(mx[0],mx[1]);
        diam[v] = max(diam[v],diam[to]);
    }
    diam[v] = max(diam[v],mx[0] + mx[1]);
    mxD[v] = mx[0];
    return mx[0];
}

int getDiam(multiset<int>& c){
    int ans = 0;
    auto it = (--c.end());
    ans += *it;
    it--;
    ans += *it;
    return ans;
}

int getMax(multiset<int>& s){
    return s.empty() ? 0 : *(--s.end());
}

void dfs2(int v,int pr = -1,int dist = 0){
    multiset<int> cur;
    cur.insert(0);
    cur.insert(0);
    cur.insert(dist);
    for(auto& to : g[v]){
        if(to == pr)
            continue;
        cur.insert(mxD[to]+1);
        st[0].insert(diam[to]);
    }

    for(auto& to : g[v]){
        if(to == pr)
            continue;
        cur.erase(cur.find(mxD[to]+1));
        st[0].insert(getDiam(cur));
        st[0].erase(st[0].find(diam[to]));
        ans = max(ans,getMax(st[0])+diam[to]+1);
        dfs2(to,v,*(--cur.end())+1);
        st[0].erase(st[0].find(getDiam(cur)));
        cur.insert(mxD[to]+1);
        st[0].insert(diam[to]);
    }
    for(auto& to : g[v]){
        if(to == pr)
            continue;
        st[0].erase(st[0].find(diam[to]));
    }
    return;
}

void solve(){
    int n;
    cin >> n;

    for(int i = 2; i <= n; i++){
        int a,b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    dfs1(1);

    ans = diam[1];

    dfs2(1);

    cout << ans << "\n";

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
//        cerr << "test = " << test << "\n";
        solve();
    }
    return 0;
}
/**
10
1 2
1 3
1 4
2 5
3 6
2 7
2 8
8 9
4 10

**/