[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;
} 

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology