[AtCoder] [經典競程 90 題] 003 - Longest Circular Road（★4）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_c
題目大意:
給你一棵樹，詢問在樹上加入一條邊後最長的環可以是多長。

---

樹直徑就會是這題答案了。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;

	vector<vector<int>> g(n);
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		g[--u].emplace_back(--v);
		g[v].emplace_back(u);
	}

	int ans = 0;
	auto dfs = [&g, &ans] (auto rec, int u, int f) -> int {
		int mx1 = 0, mx2 = 0;
		for (int v: g[u]) {
			if (v == f) continue;
			int s = rec(rec, v, u);
			if (s >= mx1) {
				mx2 = mx1;
				mx1 = s;
			} else if (s >= mx2) {
				mx2 = s;
			}
		}
		ans = max(ans, mx1 + mx2);
		return mx1 + 1;
	};
	dfs(dfs, 0, 0);
	cout << ans + 1 << '\n';
	return 0;
}