最新要闻
- 环球热点!湖北襄阳五分钟内连发两次地震:无破坏性 官方科普地震如何逃生
- 手机硬件光追 为啥一直是PPT?
- 世界快资讯丨骁龙888站起来了!小米11系列MIUI 14稳定版就绪:流畅度暴增
- 简讯:《三体》电视剧第五集惊现《GTA》地图 网友:梦幻联动、双厨狂喜
- 滴滴回来了!但没有掌声
- 车主注意!今日起 全国严查酒驾醉驾
- 环球新消息丨剧毒蓝环章鱼再现 网友:山姆超市买的、没吃直接给扔了
- 今晚油价下调!春节出行加满一箱油将少花八元
- 全球今热点:日系车后期果然省钱!丰田10年维保花费4万元 美国车最低
- 环球短讯!25年经验资深机长驾驶 3D还原尼泊尔客机坠机过程:让人后怕
- 当前报道:三星Galaxy Book 3 Pro 360笔记本来了:12核i7 还有3K触摸屏
- 【环球新要闻】70多岁大爷开40万极氪001买菜 直言此前开的奔驰真是垃圾
- 万茜吐槽自己游戏手法不行!网友发现本人玩的是《剑网3》
- 网易云音乐TV版发福利!150小时电视端会员听歌时长免费领
- 赵长江:腾势D9时速120km轮胎被磕到、车身稳如泰山
- iPhone印度造:要跟我们平分蛋糕!
广告
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
焦点报道:AcWing. 1073 树的中心
【资料图】
题目描述
给定一棵树,树中包含 \(n\) 个结点(编号\(1\)~\(n\))和 \(n-1\) 条无向边,每条边都有一个权值。
请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。
解题思路
\(\qquad\)在一棵树上,每一个节点都有两种选择,向父亲走
或者向儿子走
。
\(\qquad\)所以我们不妨进行一下分类讨论:
\(\qquad\qquad\)定义 \(ans[x]\) 为经过 \(x\) 点的最长路径,则可以分成两部分如图所示,从 \(x\) 出发向子节点走的最大距离 \(d1[x]\) 和从 \(x\) 出发向父节点走的最大距离 \(up[x]\),则 \(ans[x] = d1[x] + up[x]\)
但是可能会出现特殊情况,如下图所示:
这时候我们不能这样走了,因为重边不划算,所以我们可以维护一个次大值,当发现这种情况的时候我们就用次大值 \(d2[x]\) 加上 \(up[x]\) 来更新,如图所示为什么次大值就不会出现重边呢,这里我们采用反证法:我们先假设最大值和次大值经过同一个点,我们可以分析一下这段代码
int GoDown(int u, int fa) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue ; //遍历到父节点了 int dist = GoDown(j, u) + w[i]; // 递归子节点 //在这里的d1和d2一定是上一个子节点更新的,所以与dist找出来的子节点一定是不同的 if (dist >= d1[u]) //当d1被dist更新的时候,最长路的点是当前的点j//而次长路被之前的最长路更新过了,所以这种情况最长路和次长路在不同子节点 { d2[u] = d1[u], d1[u] = dist; pre[u] = j; } else if (dist > d2[u]) d2[u] = dist;//这种情况下,次长路被新节点更新,新节点与最长路所在的节点不同//因此不管是哪种情况都一定能保证最长路与次长路不经过同一子节点//注意只是子节点,后面的路径不能保证 } if (d1[u] == 0) leaf[u] = true ; //没被更新就是叶子,因为所有边的权重都大于0 return d1[u];}
证明完成,接下来可以直接上代码了
代码
#include #include #include using namespace std;const int N = 2e5 + 10, INF = 0x3f3f3f3f;int h[N], e[N], ne[N], w[N], idx;int d1[N], d2[N], up[N]; //d1存一个数向子节点走的最大距离,d2次大,up是向父节点走的最长距离int leaf[N], pre[N], n; //void add(int a, int b, int c) // 添加一条边a->b,边权为c{ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}int GoDown(int u, int fa) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue ; //遍历到父节点了 int dist = GoDown(j, u) + w[i]; // 递归子节点 if (dist >= d1[u]) { d2[u] = d1[u], d1[u] = dist; pre[u] = j; } else if (dist > d2[u]) d2[u] = dist; } if (d1[u] == 0) leaf[u] = true ; //没被更新就是叶子,因为所有边的权重都大于0 return d1[u];}void GoUp(int u, int fa) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue ; if (pre[u] == j) up[j] = max(d2[u], up[u]) + w[i]; else up[j] = max(d1[u], up[u]) + w[i]; GoUp(j, u); }}int main() { scanf("%d", &n); memset(h, -1, sizeof h); for (int i = 1; i < n; i ++ ) //读入树 { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w), add(v, u, w); } GoDown(1, -1), GoUp(1, -1); //以1为根节点进行DP int res = d1[1]; for (int i = 2; i <= n; i ++ ) { if (leaf[i]) res = min(res, up[i]); // 叶子节点不能向子节点走 else res = min(res, max(up[i], d1[i])); // 否则就向两个方向走 } printf("%d\n", res); return 0;}
焦点报道:AcWing. 1073 树的中心
环球热点!湖北襄阳五分钟内连发两次地震:无破坏性 官方科普地震如何逃生
每日资讯:VScode和cmake的组合拳
手机硬件光追 为啥一直是PPT?
世界快资讯丨骁龙888站起来了!小米11系列MIUI 14稳定版就绪:流畅度暴增
简讯:《三体》电视剧第五集惊现《GTA》地图 网友:梦幻联动、双厨狂喜
滴滴回来了!但没有掌声
车主注意!今日起 全国严查酒驾醉驾
【天天报资讯】计算机基础 数据类型 流程控制 字符编码 文件操作
【新视野】ARP欺骗攻击:利用driftnet截获图片数据流
环球新消息丨剧毒蓝环章鱼再现 网友:山姆超市买的、没吃直接给扔了
今晚油价下调!春节出行加满一箱油将少花八元
全球今热点:日系车后期果然省钱!丰田10年维保花费4万元 美国车最低
环球短讯!25年经验资深机长驾驶 3D还原尼泊尔客机坠机过程:让人后怕
当前报道:三星Galaxy Book 3 Pro 360笔记本来了:12核i7 还有3K触摸屏
环球焦点!portswigger 靶场之 XSS 篇(上)
每日快播:JavaWeb开发中在服务器常用命令集锦
今日热文:学习笔记——Spring管理第三方bean;Spring中Bean的作用域;Spring中Bean的生命周期;Spring中bean的后置处理器;Sp
程序员同事每天准点下班,原来是用了这6个开发工具
【NAS使用心得】使用Synology Photos管理照片
【环球新要闻】70多岁大爷开40万极氪001买菜 直言此前开的奔驰真是垃圾
万茜吐槽自己游戏手法不行!网友发现本人玩的是《剑网3》
网易云音乐TV版发福利!150小时电视端会员听歌时长免费领
赵长江:腾势D9时速120km轮胎被磕到、车身稳如泰山
iPhone印度造:要跟我们平分蛋糕!
个人使用 sudo 方法
环球视讯!iOS APP上架流程(详细)
焦点观察:聚焦技术与体验极致提升,阿里云视频云连续5年领跑!
还在用 Excel 和 SQL?火山引擎 VeDI 这款产品帮你更快处理数据
AI偷偷写70多篇新闻:数月后才被人发现
今日报丨与网易延长半年合作失败 内幕曝光:分手一事错怪暴雪了?
贾跃亭下周回国?FF发春节“回家”海报:或暗示将落地中国
【新要闻】不到3年狂揽1.41万亿元?抖音怎么做到的?
【天天热闻】特效太炸!《王者荣耀》李信新皮肤公布 碾压一念神魔
JNPF流程审批加签功能讲解
14年合作结束!暴雪网易彻底谈崩 玩家不满:暴雪甩锅被识破
紧跟特斯拉、问界!小鹏汽车宣布降价:14.89万元起
3000次超长寿命国产闪存 致态512GB SSD到手229元
资讯:印度男子得子后去尼泊尔还愿:不幸遭遇空难
马斯克曾大赞中国工人能工作到凌晨3点 特斯拉德国工人不干了
世界快讯:温州一奔驰越线撞击比亚迪 比亚迪调转180度 车头都快没了
环球速读:魔兽国服1月24日关服!暴雪称已提议延期半年 网易拒绝
图书管理系统
天天最新:Educational Codeforces Round 14
每日速读!“抠书式”还原的剧版《三体》获赞!动画版已扑街:豆瓣跌至4.6分
领券还送牙刷!三金西瓜霜牙膏狂促:6支到手23.7元
129元 小米米家保温壶上架:1.8L大容量、6小时保温75℃
国产良心!《光明记忆:无限》推出第三人称模式:女主新皮肤来了
00后女生熬夜关灯玩手机后眼部囊肿:专家科普
luckysheet踩坑记录
使用管控平台管理redis集群
当前视讯!在WPF程序中,使用Freetype显示字体
追光动画十年集大成之作!电影《长安三万里》预告曝光
AI换脸小视频泛滥网络 日本人出手:用AI检测真伪
全球快资讯丨知名经济学家:特斯拉不可能成为苹果那样的赚钱机器
热点!90后女生开比亚迪环游中国:总花费2.3万元 油费+电费还不到3千
每日消息!《流浪地球2》“人类股骨”预告发布:AI技术修复李雪健老师声音
什么是整理书包?整理书包的心得体会
计算机能力是什么意思?计算机能力一般怎么填写?
大量元素是什么意思?大量元素和微量元素有哪些?
管理报表包括哪些?管理报表和财务报表的区别有哪些?
什么是地理位置图?地理位置图用什么软件?
怎么用烤箱烤饼干?用烤箱烤饼干的做法是什么?
焦点热文:冰蝎V4.0流量分析到攻防检测
剑灵武神塔怎么进?剑灵武神塔20层苏向阳怎么打?
安卓手机相册在哪个文件夹?安卓手机相册怎么加密?
appsync是什么意思?如何安装appsync?
安卓系统怎么升级?安卓系统和鸿蒙系统哪个好?
全球热议:微软智能语音大升级:方言念古诗无压力
每日热门:特斯拉、华为问界大降价!李想:他们都得对比理想L8
环球今头条!俩小孩小区内5次放火引燃SUV 专家:熊孩子闯祸家长需兜底
每日时讯!机械硬盘大溃败:去年出货量近乎腰斩
大众、长安“缝合怪”?换代天籁消费者不买账 跌出B级车前十榜
世界热消息:学习笔记——Spring底层IOC实现;Spring依赖注入数值问题;Spring依赖注入方式
速读:FlinkSQL 时间类型转化使用小结
焦点播报:国产科幻巨制!《流浪地球2》预售票房突破4000万
微速讯:动画扑街、电视剧成神 《三体》电影版最新进展公布
嫦娥五号科研成果!中国科学家精确测定月球年龄:20.3亿年
世界快报:迪士尼联名!美特斯邦威羽绒服大促 原价500多现1百多到手
画面震撼!五菱小汽车排队“坐”火车去墨西哥
天天百事通!LibreOJ L6210 「美团 CodeM 决赛」tree
读编程与类型系统笔记09_泛型数据结构
热头条丨17岁少女晒爸爸500元买的奢侈包包遭群讽 含泪反击 结局暖心
天天热资讯!2023年我国新能源汽车销量可达950万辆:全球第一没跑 电池便宜到发指
“U盘之父”朗科房东不好当:腾讯租的15层大楼突然全退了
今日最新!1%超级富豪拿走全球三分之二新财富:穷人越来越多 专家称应财富重分配
全球消息!曾被网友戏称“候机大棚” 佛山机场花2000万改造完成
【新视野】降价后 特斯拉订单数环比涨500%!马斯克赢麻了
盗版阿凡达2合法后!Intel、微软、NV等低调回俄罗斯 身体诚实
环球信息:联想小新Pro 2023魔改140W快充 搭载新一代聚能电池有多强?
滚动:要么卸载、要么盗版!视频平台赚钱只能靠“割韭菜”:你无力反抗?
2个大厂 100亿级 超大流量 红包 架构方案 (史上最全)
VUEX 的使用学习二: state
环球时讯:我的2022
每日时讯!疑似被王思聪殴打者发声:没有赔209万 具体金额闭口不提
天天热推荐:小米最强旗舰!曝小米13 Ultra提供16+512GB版本
天天新动态:小米MIX Fold 2推送MIUI 14稳定版:系统大精简、支持光子引擎
女子网购100根仙女棒 收到100根铁丝:商家一句话噎死人
AMD Zen4锐龙终于要真正便宜了!果断坐等
【天天速看料】洛谷P2294. [HNOI2005] 狡猾的商人