Submission #63140699

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x)  { cout << "check " << x << "\n"; cout.flush();}
#define int long long
#define double long double
#define inf 0x3fffffffffffffff


//-------------- templates above --------------


void solve() {
	int n;
	cin >> n;
	vector<vector<int>> adj(n + 1);
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	vector<int> dp(n + 1, 1);
	int ans = -1;
	auto dfs = [&] (auto self, int x, int fa) -> void {
		vector<int> a;
		for (auto y : adj[x]) {
			if (y == fa) {
				continue;
			}
			self(self, y, x);
			a.push_back(dp[y]);
			if (adj[x].size() >= 1 && adj[y].size() >= 4) {
				ans = max(ans, dp[y] + 1);
			}
		}
		sort(a.begin(), a.end(), greater());
		if (a.size() >= 4) {
			ans = max(ans, a[0] + a[1] + a[2] + a[3] + 1);
		}
		if (a.size() >= 3) {
			dp[x] = a[0] + a[1] + a[2] + 1;
		}
	};
	dfs(dfs, 1, 0);
	cout << ans << "\n";
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	while (T--) {
		solve();
	}
	return 0;
}

Submission Info

Judge Result