【題解】Zerojudge b967 - 第 4 題 血緣關係

題目連結

題目大意

給定一棵樹，求最遠對點的距離。

題解

題目要求找最遠的對點，其實就是在找樹直徑。以下提供一種作法。

挑選任意節點作為樹根。對於兩個相鄰的節點 $u$ 和 $v$，假設 $v$ 在 $u$ 的子樹，在 dfs $u$ 的子孫的過程中我們順便紀錄遍歷到目前為止到葉節點最深的深度。當我們遍歷新的子孫時，答案要馬不變，要馬變成 $depth[u] + depth[v] + 1$，相當於合併 $u$ 到葉節點和 $v$ 到葉節點兩條路徑。以上的過程都可以在一次 dfs 中完成，因此時間複雜度為 $O(n)$。

在 Zerojudge 更新之後 judge 跑的更慢了。現在 cin / cout 加上 ios::sync_with_stdio(false) 和 cin.tie(0) 還是會吃 TLE，改成使用 scanf 和 printf 才勉強壓進 $3$ 秒內。IO 優化的技巧可以參考我寫的【筆記】IO 優化這篇文章。

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

int main() {
	int n;
	while(scanf("%d", &n) != EOF) {
		vector<vector<int>> g(n);
		for(int i = 0; i < n - 1; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		vector<int> depth(n);
		int ans = 0;
		auto dfs = [&](auto dfs, int u, int p) -> void {
			for(auto v : g[u]) {
				if(v == p) {
					continue;
				}
				dfs(dfs, v, u);
				ans = max(ans, depth[u] + depth[v] + 1);
				depth[u] = max(depth[u], depth[v] + 1);
			}
		};
		dfs(dfs, 0, -1);
		printf("%d\n", ans);
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge b967 - 第 4 題 血緣關係