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

[bzoj 3124][sdoi 2013 省选] 直径

Description

小Q最近学习了一些图论知识。根据课本,有如下定义。树:无回路且连通的无向图,每条边都有正整数的权值来表示其长度。如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)
表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。
直径:一棵树上,最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道,对于给定的一棵树,其直径的长度是多少,以及有多少条边满足所有的直径都经过该边。

Input

第一行包含一个整数N,表示节点数。
接下来N-1行,每行三个整数a, b, c ,表示点 a和点b之间有一条长度为c
的无向边。

Output

共两行。第一行一个整数,表示直径的长度。第二行一个整数,表示被所有
直径经过的边的数量。

Sample Input

6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100

Sample Output

1110
2

【样例说明】
直径共有两条,3 到2的路径和3到6的路径。这两条直径都经过边(3, 1)和边(1, 4)。

Hint

对于100%的测试数据:2≤N≤200000,所有点的编号都在1..N的范围内,

边的权值≤10^9。

#include

相关文章:

  • [hdu 3652] B-number
  • JavaScript [学习笔记]
  • [2016.7.Test1] T1 三进制异或
  • [2016.7.test1] T2 偷天换日 [codevs 1163 访问艺术馆(类似)]
  • Linux操作系统下共享文件夹设置方法介绍
  • [单调队列] day.1
  • 二分图大讲堂——彻底搞定最大匹配数(最小覆盖数)、最大独立数、最小路径覆盖、带权最优匹配
  • 有向强连通和网络流大讲堂——史无前例求解最大流(最小割)、最小费用最大流
  • [2016.7 Day.4] T1 游戏 [正解:二分图 偏解:奇葩贪心+模拟?(不知如何称呼不过居然比std还快)]
  • [2016.7 day.5] T2
  • [2016.7 test.5] T1
  • [hdu 4552] 怪盗基德的挑战书
  • 从头到尾彻底理解KMP
  • KMP模板
  • GNU g++常用编译选项用法
  • JS中 map, filter, some, every, forEach, for in, for of 用法总结
  • [译]Python中的类属性与实例属性的区别
  • CentOS学习笔记 - 12. Nginx搭建Centos7.5远程repo
  • Consul Config 使用Git做版本控制的实现
  • CSS魔法堂:Absolute Positioning就这个样
  • ES6简单总结(搭配简单的讲解和小案例)
  • Gradle 5.0 正式版发布
  • Javascripit类型转换比较那点事儿,双等号(==)
  • JAVA多线程机制解析-volatilesynchronized
  • jdbc就是这么简单
  • JS数组方法汇总
  • MobX
  • Python代码面试必读 - Data Structures and Algorithms in Python
  • RedisSerializer之JdkSerializationRedisSerializer分析
  • Redis在Web项目中的应用与实践
  • SQLServer之创建显式事务
  • 半理解系列--Promise的进化史
  • 程序员最讨厌的9句话,你可有补充?
  • ------- 计算机网络基础
  • 前端面试之闭包
  • 突破自己的技术思维
  • 用jquery写贪吃蛇
  • 再谈express与koa的对比
  • 在Mac OS X上安装 Ruby运行环境
  • (9)STL算法之逆转旋转
  • (C语言)求出1,2,5三个数不同个数组合为100的组合个数
  • (分布式缓存)Redis持久化
  • (附源码)ssm学生管理系统 毕业设计 141543
  • (力扣)循环队列的实现与详解(C语言)
  • (全注解开发)学习Spring-MVC的第三天
  • (一一四)第九章编程练习
  • (转)IIS6 ASP 0251超过响应缓冲区限制错误的解决方法
  • (转)程序员疫苗:代码注入
  • .NET CLR Hosting 简介
  • .net core webapi Startup 注入ConfigurePrimaryHttpMessageHandler
  • .NET 应用架构指导 V2 学习笔记(一) 软件架构的关键原则
  • .考试倒计时43天!来提分啦!
  • @Bean有哪些属性
  • [2013][note]通过石墨烯调谐用于开关、传感的动态可重构Fano超——
  • [Android]使用Retrofit进行网络请求