Cod sursa(job #3159948)

Utilizator IanisBelu Ianis Ianis Data 22 octombrie 2023 15:45:06
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
 
#ifndef LOCAL
#define endl '\n'
#endif
 
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
 
#define fi first
#define se second
 
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
 
#define lsb(x) (x & (-x))
 
using namespace std;
 
#define double long double
 
typedef long long ll;
typedef pair<int, int> pii;
 
const int NMAX = 1e5+5;
const int INF = 1e9+5;
 
int n;
vector<pii> g[NMAX];
int dp1[NMAX], dp2[NMAX];
 
void read() {
	cin >> n;
	for (int i = 1, x, y; i < n; i++) {
		cin >> x >> y;
		g[x].push_back({0, y});
		g[y].push_back({0, x});
	}
}
 
void solve(int x = 1, int p = 0) {
	if (sz(g[x]) <= 1 - (x == 1)) return;
	for (auto &[dist, it] : g[x]) {
		if (it == p) {
			dist = -1;
			continue;
		}
		solve(it, x);
		dist = dp2[it] + 1;
	}
	sort(all(g[x]), greater<pii>());
	dp2[x] = g[x][0].fi;
	dp1[x] = dp2[x];
	if (sz(g[x]) >= 3 - (x == 1))
		dp1[x] = g[x][0].fi + g[x][1].fi;
}
 
signed main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#else
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);
#endif
 
	int t = 1;
//	cin >> t;
 
	while (t--) {
		read();
		solve();
		int ans = 0;
		for (int i = 1; i <= n; i++)
			ans = max(ans, dp1[i]);
		cout << ans << endl;
	}
 
	return 0;
}