当前位置: 首页 > news >正文

算法提高之树的中心

算法提高之树的中心

  • 核心思想:树形dp + 换根dp

    • 每个点作为根节点 找其子树的最大距离和父节点的最大距离

    • dfs1:求子树对于当前根节点的最大距离和次大距离

      • 求次大距离原因:如果当前节点是其父节点子树的最大路径上的点,最大距离不能用
      • 在这里插入图片描述
    • dfs2:找父节点以上的最长距离

  •   #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 10010,M=N<<1,INF=0x3f3f3f3f;int n;int h[N],e[M],ne[M],w[M],idx;int d1[N],d2[N],up[N];int s1[N],s2[N];  //s1存该点最大距离从哪个点过来 s2存次大距离...void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}void dfs1(int u,int father){for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j == father) continue;dfs1(j,u);if(d1[j] + w[i] >= d1[u]){d2[u] = d1[u],d1[u] = d1[j]+w[i];s2[u] = s1[u],s1[u] = j;}else if(d1[j] + w[i]> d2[u]){d2[u] = d1[j]+w[i] , s2[u] = j;}}}void dfs2(int u,int father){for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==father) continue;//如果j为求最大距离时用的点 d1[u]不能用if(s1[u] == j) up[j] = w[i] + max(up[u],d2[u]);  else up[j] = w[i] + max(up[u],d1[u]);dfs2(j,u);}}int main(){memset(h,-1,sizeof h);cin>>n;for(int i=1;i<n;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c) , add(b,a,c);}dfs1(1,-1);dfs2(1,-1);int res=INF;for(int i=1;i<=n;i++) res = min(res,max(d1[i],up[i]));cout<<res<<endl;}
    

相关文章:

算法提高之树的中心

算法提高之树的中心 核心思想&#xff1a;树形dp 换根dp 每个点作为根节点 找其子树的最大距离和父节点的最大距离 dfs1&#xff1a;求子树对于当前根节点的最大距离和次大距离 求次大距离原因&#xff1a;如果当前节点是其父节点子树的最大路径上的点&#xff0c;最大距离不…...

【Java基础】面向对象是什么

面向对象和面向过程的对比 类和对象 class Car{} 是描述对象&#xff08;车&#xff09;的类&#xff0c;属于引用数据类型用来描述对象具有的属性(变量)和行为(函数)&#xff0c;属于概念模型 Car baomanew Car(); 对象需要由类来创建对象具备了类中定义的属性和行为 对象…...

家用洗地机应该怎么选?哪个牌子好?市场上主流洗地机品牌推荐

洗地机的出现&#xff0c;让越来越多的家庭享受清洁的过程&#xff0c;给人们腾出来更多的时间陪伴家人和休息。但是在选购一台洗地机前&#xff0c;大家多多少少肯定有些疑问&#xff0c;洗地机到底实不实用&#xff1f;好不好用&#xff1f;能扫干净吗&#xff1f;还有哪些好…...

python Django REST framework允许你根据API的版本提供不同的行为或数据

在Django REST framework中,版本控制是一个重要的功能,它允许你根据API的版本提供不同的行为或数据。以下是如何在Django REST framework中设置API版本控制的几种方法: 1. 使用URL路径参数 你可以通过URL路径中的参数来指定API的版本。例如: python复制 # urls.py from …...

unity给物体添加可以包裹所有子物体的BoxCollider

代码如下可直接调用 MeshTool.SpawnCollider(mode);using UnityEngine;public class MeshTool {public static Bounds SpawnCollider(Transform target){Vector3 pMax Vector3.zero;Vector3 pMin Vector3.zero;Vector3 center Vector3.zero;Vector3 oldPos target.transfor…...

2024五一数学建模A题思路代码与论文分析

2024五一数学建模A题完整代码和成品论文获取↓↓↓↓↓ https://www.yuque.com/u42168770/qv6z0d/gyoz9ou5upvkv6nx?singleDoc# 2024五一数学建模A题钢板最优切割路径问题需要建立的模型和算法: 图论 最短路径算法(Dijkstra算法、Floyd算法等) 动态规划 网格化离散建模 …...

ICode国际青少年编程竞赛- Python-1级训练场-基础训练2

ICode国际青少年编程竞赛- Python-1级训练场-基础训练2 1、 a 4 # 变量a存储的数字是4 Dev.step(a) # 因为变量a的值是4&#xff0c;所以Dev.step(a)就相当于Dev.step(4)2、 a 1 # 变量a的值为1 for i in range(4):Dev.step(a)Dev.turnLeft()a a 1 # 变量a的值变为…...

科技控必看!让你轻松成为机器人领域达人

科技控们注意了&#xff01;你是不是经常对机器人技术充满无限的好奇&#xff0c;却又因为缺乏合适的渠道而难以深入了解和亲身体验呢&#xff1f;别担心&#xff0c;BFT机器人&#xff0c;正是你探索机器人世界的绝佳之地&#xff01; 在这里&#xff0c;你将发现一个充满惊喜…...

Linux进程——Linux下常见的进程状态

前言&#xff1a;在进程学习这一块&#xff0c;我们主要学习的就是PCB这个进程控制块&#xff0c;而PBC就是用来描述进程的结构体&#xff0c;而进程状态就是PCB结构体中的一个变量。 本篇主要内容&#xff1a; 操作系统中的进程状态Linux下的进程状态 在开始之前&#xff0c;我…...

TCP长连接短链接

1、短连接 短连接是指通讯双方有数据交互时&#xff0c;就建立一个连接&#xff0c;数据发送完成后&#xff0c;则断开此连接&#xff0c;即每次连接只完成一项业务的发送。 2、长连接 长连接是指在一个连接上可以连续发送多个数据包&#xff0c;在连接保持期间&#xff0c;…...

代码随想录35期Day33-Java

Day33题目 LeetCode1005:K 次取反后最大化的数组和 核心思想&#xff1a;每次取反都取反最小的。如果有负数&#xff0c;则一直取反最小的负数&#xff0c;如果没有就取反正数。取反次数只需要看是奇数还是偶数。偶数则正数序列不变&#xff0c;奇数则最小的变成负数 class …...

PMP考试没过怎么办?如何补考?(附复核流程)

最近刷小红书&#xff0c;看很多人都在晒PMP通过的成绩截图&#xff0c;一方面为大家开心&#xff0c;终于拿到了期盼已久的PMP&#xff0c;但同时也有宝子发挥失常没通过考试&#xff0c;所以这期针对没考过的宝子们&#xff0c;出一期复盘文章&#xff0c;无论结果如何&#…...

自主实现Telnet流量抓取

自主实现Telnet流量抓取 根据测试需求&#xff0c;需要抓取Telnet流量包&#xff0c;使用wireshark Python&#xff08;socket、telnetlib库&#xff09;实现 实现代码 主要此处有坑&#xff0c; 根据协议规则&#xff0c;wireshark 默认端口为23 的是Telnet协议&#xff0…...

以瓦片地图为底图添加图表,保留拖拽功能

1、问题1 在地图上覆盖一个容器层&#xff0c;容器层上的内容显示不出来如何解决&#xff1f; 原因&#xff1a;堆叠指数问题 解决方案&#xff1a;绝对定位后&#xff0c;提升其z-index值即可 2、问题2 在地图上覆盖一个容器层&#xff0c;影响了地图拖拽&#xff0c;如何…...

Windows cmd bat之特殊符号及变量

cmd 常用变量 bat批处理常用命令 %1~%9表示拖入文件&#xff08;%0以外的输入文件&#xff09;,%0表示批处理文件本身 %0~%1字母意思基本相同&#xff0c;不区分大小写 ::打印当前窗口地址 echo “%cd%” %0 获取当前文件路径 %~d0 …...

用python写个控制MicroSIP自动拨号和定时呼叫功能(可用在小型酒店叫醒服务)

首先直接上结果吧&#xff0c;MicroSIP 助手&#xff0c;控制MicroSIP自动拨号&#xff0c;定时呼叫的非常实用小工具&#xff01; 在使用MicroSIP 助手之前&#xff0c;我们需要了解MicroSIP是什么&#xff0c;MicroSIP是一个SIP拨号软件&#xff0c;支持注册任意SIP平台实现拨…...

axios 取消token 模糊搜索

import axios from ‘axios’; // 创建一个取消令牌源&#xff08;cancel token source&#xff09; const CancelToken axios.CancelToken; const source CancelToken.source(); // 下拉框搜索函数 function search() { // 获取输入值 const inputValue document.getElem…...

【OTS4WORD】“精简并行过程”——容易剪裁的“软件过程改进方法和规范”模板

附件资源是作者针对SPP采用模板重新格式化打包制作&#xff0c;原模板具有格式不受控的缺点&#xff0c;导致文档编制过程中引起不必要的排版麻烦。 附件资源适用于希望改进工作流程&#xff0c;适配CMMI质量管理体系的公司或个人使用&#xff0c;质量改进管理组织、项目管理组…...

22 | MySQL有哪些“饮鸩止渴”提高性能的方法?

短连接风暴 第一种方法:先处理掉那些占着连接但是不工作的线程。 kil id 第二种方法:减少连接过程的消耗。 让数据库跳过权限验证阶段,重启数据库,并使用–skip-grant-tables 参数启动。 慢查询性能问题 索引没有设计好 创建索引都支持 Online DDL 了,对于那种高峰期数…...

【AIGC调研系列】VILA-1.5版本的视频理解功能如何

VILA-1.5版本的视频理解功能表现出色&#xff0c;具有显著的突破。这一版本不仅增强了视频理解能力&#xff0c;还提供了四种不同规模的模型供用户选择&#xff0c;以适应不同的应用需求和计算资源限制[1][2][3]。此外&#xff0c;VILA-1.5支持在笔记本等边缘设备上部署&#x…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...