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

P1131 [ZJOI2007] 时态同步

Portal.

先找出树上以 S S S 为起点最长的一条链,然后让其他链的长度都和该链对齐即可。

维护每个结点 x x x 的子树最长链 d max ⁡ ( x ) d_{\max}(x) dmax(x),则每次 DFS 求出最长链之后调整对齐的代价为 d max ⁡ ( x ) − ( d max ⁡ ( s o n x ) + w i ) d_{\max}(x)-(d_{\max}(son_x)+w_i) dmax(x)(dmax(sonx)+wi)

#include <bits/stdc++.h>
using namespace std;
#define int long longconst int maxn=5e5+5;
int head[maxn],V,cnt,mxd[maxn];
struct edge{int to,nxt,w;}e[maxn];void add(int x,int y,int z){e[++cnt]=(edge){y,head[x],z},head[x]=cnt;}void dfs(int x,int fa)
{for(int i=head[x];i;i=e[i].nxt){if(e[i].to==fa) continue;dfs(e[i].to,x),mxd[x]=max(mxd[x],mxd[e[i].to]+e[i].w);}for(int i=head[x];i;i=e[i].nxt){if(e[i].to==fa) continue;V+=mxd[x]-(mxd[e[i].to]+e[i].w);}
}signed main()
{int N,S;cin>>N>>S;for(int i=1,a,b,t;i<N;i++) cin>>a>>b>>t,add(a,b,t),add(b,a,t);dfs(S,0);cout<<V;return 0;
}

相关文章:

P1131 [ZJOI2007] 时态同步

Portal. 先找出树上以 S S S 为起点最长的一条链&#xff0c;然后让其他链的长度都和该链对齐即可。 维护每个结点 x x x 的子树最长链 d max ⁡ ( x ) d_{\max}(x) dmax​(x)&#xff0c;则每次 DFS 求出最长链之后调整对齐的代价为 d max ⁡ ( x ) − ( d max ⁡ ( s o …...

springboot(ssm 旅游管理系统 旅游规划平台 Java(codeLW)

springboot(ssm 旅游管理系统 旅游规划平台 Java(code&LW) 开发语言&#xff1a;Java 框架&#xff1a;ssm/springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff1a;mysql 5.7&#xff08;或8.0&#xff…...

C++ 构造函数不能是虚函数的原因

构造函数不能被声明为虚函数的主要原因涉及到对象的创建和初始化过程以及虚函数的工作机制。下面详细解释为什么构造函数不能是虚函数&#xff1a; 1.构造函数的调用顺序&#xff1a; 构造函数用于创建对象&#xff0c;并且对象的构造是在派生类构造函数之前完成的。当你创建…...

【LearnOpenGL基础入门——2】搭建第一个OpenGL窗口

目录 一.配置GLFW 二.配置GLAD 三.第一个OpenGL窗口 3.1 GLFW设置 3.2 GLAD设置 3.3 视口 3.4 输入 3.5渲染 在我们画出出色的效果之前&#xff0c;首先要做的就是创建一个OpenGL上下文(Context)和一个用于显示的窗口。然而&#xff0c;这些操作在每个系统上都是不一样…...

第三章:人工智能深度学习教程-人工智能与机器学习与深度学习之间的区别

人工智能基本上是通过一组规则&#xff08;算法&#xff09;将人类智能融入机器的机制。人工智能是两个词的组合&#xff1a;“人工”是指由人类或非自然物体制造的东西&#xff0c;“智能”是指相应地理解或思考的能力。另一个定义可能是“人工智能基本上是训练机器&#xff0…...

vue中 process.env 对象为空对象问题

问题&#xff1a;今天在处理vue项目环境问题的时候&#xff0c;发现直接打印 process 对象和打印 process.env 时 env 对象输出结果是不一样的&#xff0c;如下图所示&#xff1a; 在网上搜索了一番后发现还是有挺多朋友对此感到疑惑的&#xff0c;询问了同事&#xff0c;同…...

uniapp小程序v-for提示“不支持循环数据”

问题描述: 在uniapp小程序项目中使用多层for循环时&#xff0c;小程序端提示&#xff1a;uniapp v-for 暂不支持循环数据&#xff0c;以至于获取不到循环的数据。 <view v-for"(item,index) in list" :key"item.id"> <view v-for"child i…...

CROS错误 403 preflight 预检

预检 403 响应 Response for preflight 403 forbidden 如上图&#xff0c;配置了请求接口一直报错&#xff0c;前端看了没有什么问题&#xff0c;不知道哪里报错了&#xff0c;那么可能是后端没有设置跨域。&#xff08;或者是设置了&#xff0c;但是可能需要换一种方式&#…...

nginx参数调优能提升多少性能

前言 nginx安装后一般都会进行参数优化&#xff0c;网上找找也有很多相关文章&#xff0c;但是这些参数优化对Nginx性能会有多大影响&#xff1f;为此我做个简单的实验测试下这些参数能提升多少性能。 声明一下&#xff0c;测试流程比较简单&#xff0c;后端服务也很简单&…...

用友U8 Cloud 反序列化RCE漏洞复现

0x01 产品简介 用友U8 Cloud是用友推出的新一代云ERP&#xff0c;主要聚焦成长型、创新型企业&#xff0c;提供企业级云ERP整体解决方案。 0x02 漏洞概述 用友U8 Cloud存在多处&#xff08;FileManageServlet和LoginVideoServlet&#xff09;反序列化漏洞&#xff0c;系统未将…...

acwing算法基础之数据结构--STL简介

目录 1 基础知识2 模板3 使用示例3.1 vector3.2 pair3.3 string3.4 queue 1 基础知识 无。 2 模板 vector, 变长数组&#xff0c;倍增的思想size() 返回元素个数empty() 返回是否为空clear() 清空front()/back() 使用时&#xff0c;必须判断向量类容器非空push_back()/po…...

【Python深入学习】- 书籍推荐|数据结构和算法介绍|内建集合数据类型

&#x1f308;个人主页: Aileen_0v0 &#x1f525;系列专栏:PYTHON学习系列专栏 &#x1f4ab;"没有罗马,那就自己创造罗马~" 若把编写代码比作行军打仗&#xff0c;那么要想称霸沙场&#xff0c;不能仅靠手中的利刃&#xff0c;还需深谙兵法。Python是一把利刃&…...

物联网对接协议

物联网对接协议有很多种&#xff0c;以下是几种常见的物联网对接协议&#xff1a; Modbus&#xff1a;是一种强大的通信标准&#xff0c;广泛应用于工业自动化和SCADA系统&#xff0c;以便将仪表、传感器和执行器的信号发送回主控制器。 Modbus具有广泛的通信协议&#xff0c;…...

腾讯待办关停,导出的数据怎么恢复到手机上面?

相信有不少腾讯待办的用户都发现了其“业务关停通知”&#xff0c;确实如此&#xff0c;由于业务调整&#xff0c;腾讯待办将于2023年的12月20日全面停止运营并下架&#xff0c;这就表示以后我们无法继续使用它了。在腾讯待办关停之前&#xff0c;绝大多数用户需要做的就是及时…...

视频特效编辑软件 After Effects 2022 mac中文版介绍 (ae 2022)

After Effects 2022 mac是一款视频特效编辑软件&#xff0c;被称为AE&#xff0c;拥有强大的特效工具&#xff0c;旋转&#xff0c;用于2D和3D合成、动画制作和视觉特效等&#xff0c;效果创建电影级影片字幕、片头和过渡&#xff0c;是一款可以帮助您高效且精确地创建无数种引…...

innovus:解决报告复制时一行拆成两行的问题

我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起来吧&#xff1f; innovus复制报告时一行的东西出现在两行上&#xff0c;解决只需要一条命令: set_table_style -no_frame_width...

MySQL数据脱敏(Data masking plugin functions)

对于企业而言&#xff0c;数据脱敏可以在数据共享或测试时用于保护敏感数据&#xff08;如信用卡&#xff0c;社保卡&#xff0c;地址等&#xff09;。通过对敏感数据进行脱敏处理&#xff0c;组织可以最大限度地降低数据泄露和未经授权访问的风险&#xff0c;同时仍能够使用真…...

Flutter 07 框架和三棵树(Widgets、Elements和RenderObjects)

一、Flutter框架的整体结构&#xff1a; Flutter是Google推出并开源的跨平台开发框架&#xff0c;主打跨平台、高保真、高性能。开发者可以通过Dart语 言开发Flutter应用&#xff0c;一套代码同时运行在ios和Android平台。不仅如此&#xff0c;Flutter还支持Web、桌面、嵌 入应…...

EasyExcel 导出冻结指定行

导出的实体类 package org.jeecg.modules.eis.test;import com.alibaba.excel.annotation.ExcelProperty; import com.alibaba.excel.annotation.write.style.*; import lombok.Getter; import lombok.Setter; import org.apache.poi.ss.usermodel.HorizontalAlignment;import…...

ke9案例三:页面提交文件,我服务器端接收

案例三:页面提交文件,我服务器端接收 ProcessFile.java 1value "/process-file" 2获取邮件消息的所有部分part--Collection<Part> partsrequest.getParts(); 3遍历每一个part 4之后可以打印头文件等String headerpart.getHeader("content-disposition&q…...

springboot调用第三方接口json转换成对象

请求接口是一个比较常见的需求&#xff0c;接口返回一般是一个json类型&#xff0c;需要进行组装成对应的类&#xff0c;例 {"status_code": 200,"message": "success","data": {"cost": 286.6933,"bom_list": […...

uniapp使用vue3和ts开发小程序自定义tab栏,实现自定义凸出tabbar效果

要实现自定义的tabbar效果&#xff0c;可以使用自定义tab覆盖主tab来实现&#xff0c;当程序启动或者从后台显示在前台时隐藏自带的tab来实现。自定义一个tab组件&#xff0c;然后在里面实现自定义的逻辑。 组件中所使用的组件api可以看&#xff1a;Tabbar 底部导航栏 | uView…...

麒麟信安获批牵头成立国家关键领域信创行业产教融合共同体

日前&#xff0c;由麒麟信安、长沙理工大学、长沙职业技术学院联合牵头成立的国家关键领域信创行业产教融合共同体&#xff08;以下简称&#xff1a;共同体&#xff09;已获湖南省教育厅批准&#xff0c;并推荐至教育部。 目前共同体已吸引10余家联盟单位及全国20余家企业、高…...

好消息,微信消费者投诉工具升级,可以直接回复用户、处理投诉了。。。

大家好&#xff0c;我是小悟 兄弟们&#xff0c;阅读本文之前&#xff0c;建议先阅读【连夜干出来一个自动处理【微信消费者投诉管理系统】&#xff0c;支持多商户】。 为了使工具更好用&#xff0c;也为帮助商户更好地处理消费者投诉&#xff0c;提升用户满意度&#xff0c;…...

手动修复 rabbitmq 报错 “Crash dump is being written to“

rabbitmq 报错: 2023-11-07 16:38:52.682 [error] emulator Error in process <0.368.0> on node rabbitrabbitmq-0.rabbitmq-discovery.openstack.svc.cluster.local with exit value: {shutdown,[{mnesia_loader,handle_exit,2,[{file,"mnesia_loader.erl"}…...

日志门面技术

1.JCL public abstract class LogFactory {public static Log getLog(Class clazz) throws LogConfigurationException {// 默认实现类为LogFactoryImplreturn getFactory().getInstance(clazz);} }利用LogFactoryImpl实例化具体的日志框架。其中&#xff0c;如果存在log4j依赖…...

机器人制作开源方案 | 管内检测维护机器人

一、作品简介 作者&#xff1a;李泽彬&#xff0c;李晋晟&#xff0c;杜张坤&#xff0c;禹馨雅 单位&#xff1a;运城学院 指导老师&#xff1a;薛晓峰 随着我国的社会主义市场经济的飞速发展和科学技术的革新&#xff0c;各行各业的发展越来越离不开信息化和网络化的…...

k8s存储卷

目录 1、emptyDir存储卷 2、hostPath存储卷 3、nfs共享存储卷 4、PVC 和 PV 4.1 PV和PVC之间的相互作用遵循这个生命周期&#xff1a; 4.2 PV的状态 4.3 一个PV从创建到销毁的具体流程如下&#xff1a; 静态PVC&#xff1a; 动态PVC 1、emptyDir存储卷 当Pod被分配给节…...

View 自定义 - 属性 xml

一、概念 在 xml 中为控件设置的属性。自定义属性名称如果使用系统已定义的&#xff0c;例如 textSize 会在编译时报错。 格式类型定义/使用 string 字符串 <attr name "myContent" format "color" /> android:myContent "Hello Word!&quo…...

2007-2022年全国各地级市金融机构网点数据

2007-2022年地级市金融机构网点数据 1、时间&#xff1a;2007-2022年 2、指标&#xff1a;行政区划代码、年份、城市名称、所属省份、银行网点数量、其中-政策性银行及国家开发银行营业网点占比、其中-商业银行营业网点数量占比、其中-农村金融机构营业网点数量占比 3、范围…...