題目大意
給定一棵樹,求最遠對點的距離。
題解
題目要求找最遠的對點,其實就是在找樹直徑。以下提供一種作法。
挑選任意節點作為樹根。對於兩個相鄰的節點 $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 題 血緣關係
0 留言