树的基础
2022/8/12 23:27:04
本文主要是介绍树的基础,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
写这个是因为觉得不能颓废了,基础不行就得补
基础之基础
没啥好说的,看oiwiki
!!!重点是一定要区分无向和有向
树的直径/重心
发现一个很良心的博客blog。
这模板题也是他出的
树的直径
#include<bits/stdc++.h> using namespace std; #define ll long long #define LLF LLONG_MAX const int N=1e6; struct sss{ int v,nxt; ll val; }T[N<<1]; int head[N]; int tot; ll ans=-LLF; ll f[N]; void add(int u,int v,ll w) { T[++tot].v=v; T[tot].val=w; T[tot].nxt=head[u]; head[u]=tot; } void dfs(int u,int fa) { f[u]=0; for(int i=head[u];i;i=T[i].nxt) { int v=T[i].v; if(v==fa)continue; dfs(v,u); ans=max(ans,f[u]+f[v]+T[i].val); f[u]=max(f[u],f[v]+T[i].val); } } int main() { int n; scanf("%d",&n); int u,v; ll w; for(int i=1;i<n;i++) { scanf("%d%d%lld",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,1); printf("%lld",ans); return 0; }
这篇关于树的基础的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?