树的中心
2022/9/16 6:18:37
本文主要是介绍树的中心,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://www.acwing.com/problem/content/1075/
输出树的中心(该点到树中其他结点的最远距离最近)。
时间复杂度 \(O(n)\)。
#include <bits/stdc++.h> using namespace std; #define LL long long int main(){ ios::sync_with_stdio(false);cin.tie(0); int n; cin >> n; vector < vector < array<LL, 2> > > e(n + 1); for (int i = 1; i < n; i ++ ){ int u, v, w; cin >> u >> v >> w; e[u].push_back({w, v}); e[v].push_back({w, u}); } vector <LL> d1(n + 1), d2(n + 1), s1(n + 1), s2(n + 1); function<void(int, int)> dfs1 = [&](int u, int fa){ for (auto [w, v] : e[u]){ if (v == fa) continue; dfs1(v, u); LL x = d1[v] + w; if (x > d1[u]){ d2[u] = d1[u], s2[u] = s1[u]; d1[u] = x, s1[u] = v; } else if (x > d2[u]){ d2[u] = x, s2[u] = v; } } }; dfs1(1, 0); vector <LL> up(n + 1); function<void(int, int)> dfs2 = [&](int u, int fa){ for (auto [w, v] : e[u]){ if (v == fa) continue; if (s1[u] == v) up[v] = max(up[u], d2[u]) + w; else up[v] = max(up[u], d1[u]) + w; dfs2(v, u); } }; dfs2(1, 0); LL ans = 1e18; for (int i = 1; i <= n; i ++ ) ans = min(ans, max(d1[i], up[i])); cout << ans << "\n"; return 0; }
这篇关于树的中心的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding