当前位置: 首页 > 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…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...