BZOJ 1060: [ZJOI2007]时态同步( 树形dp )
坑爹...数据是错的..详见discuss http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1060
先求根到叶子的距离最大值x, 然后把所有叶子到根的距离变成x. 要使增加的最少, 就要利用不同叶子到根的路径的重复部分...然后各种乱搞就可以了..
-----------------------------------------------------------------------------------
int main() {
-----------------------------------------------------------------------------------
1060: [ZJOI2007]时态同步
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1774 Solved: 458
[Submit][Status][Discuss]
Description
小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成,我们不妨称之为节点,并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接,且对于电路板的任何两个节点,都存在且仅存在一条通路(通路指连接两个元件的导线序列)。在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后,产生一个激励电流,通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后,得到信息,并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终,激烈电流将到达一些“终止节点”——接收激励电流之后不再转发的节点。激励电流在导线上的传播是需要花费时间的,对于每条边e,激励电流通过它需要的时间为te,而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路——即保持时态同步。由于当前的构造并不符合时态同步的要求,故需要通过改变连接线的构造。目前小Q有一个道具,使用一次该道具,可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步?
Input
第一行包含一个正整数N,表示电路板中节点的个数。第二行包含一个整数S,为该电路板的激发器的编号。接下来N-1行,每行三个整数a , b , t。表示该条导线连接节点a与节点b,且激励电流通过这条导线需要t个单位时间
Output
仅包含一个整数V,为小Q最少使用的道具次数
Sample Input
1
1 2 1
1 3 3
Sample Output
HINT
【数据规模】
对于100%的数据,N ≤ 500000
对于所有的数据,te ≤ 1000000
Source
最新文章
- After the exam
- linux常用vi命令
- ViewPager+Fragment再探:和TAB滑动条一起三者结合
- JMeter工具的使用-ForEach
- [CAMCOCO][C#]我的系统架构.服务器端.(四)----Model层 实体的自我验证
- js高程笔记1-3章
- mysql快速上手2
- nvidia安装与卸载方式
- void (*f(int, void (*)(int)))(int) 函数解析
- python3.4 使用pymssql 乱码
- 通过设置Referer反";反盗链";
- asp.net mvc 上传附件验证
- HDU 5823 color II
- React组件开发(一)初识React
- ASP.NET WebApi 使用Swagger生成接口文档
- Eclipse安装TestNG插件
- linux下升级gcc版本(gcc-7)
- DevExpress v18.1新版亮点——Reporting篇(三)
- STM32CubeF4 FreeRTOS Examples don't work correctly with HAL_GetTick
- C#委托、事件剖析(上)
热门文章
- datatable,查询,排序,复制等操作
- python自学笔记(三)python基本数据类型之列表list
- wireshark 包分析命令
- selenium 学习笔记 ---新手学习记录(2) 问题总结
- javascript的isPrototypeOf函数的理解
- RESTClient 控件 从服务器获得数据集 REST
- C++标准程序库的输入输出流(I/O Stream)复制文件(4种方法)
- jQuery.merge 源码阅读
- HDOJ 1003 Max Sum(线性dp)
- 改变status bar的状态