codevs2370 小机房的树
2024-08-30 02:58:06
题目描述 Description
小机房有棵焕狗种的树,树上有N个节点,节点标号为0到N-1,有两只虫子名叫飘狗和大吉狗,分居在两个不同的节点上。有一天,他们想爬到一个节点上去搞基,但是作为两只虫子,他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量(从父亲节点爬到此节点也相同),他们想找出一条花费精力最短的路,以使得搞基的时候精力旺盛,他们找到你要你设计一个程序来找到这条路,要求你告诉他们最少需要花费多少精力
输入描述 Input Description
第一行一个n,接下来n-1行每一行有三个整数u,v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ,v 表示两只虫子所在的节点
输出描述 Output Description
一共有m行,每一行一个整数,表示对于该次询问所得出的最短距离。
样例输入 Sample Input
3
1 0 1
2 0 1
3
1 0
2 0
1 2
样例输出 Sample Output
1
1
2
数据范围及提示 Data Size & Hint
1<=n<=50000, 1<=m<=75000, 0<=c<=1000
最新文章
- Mybatis框架的模糊查询(多种写法)、删除、添加(四)
- Mysql数据库之Binlog日志使用总结
- 最简单的Android教程之自定义控件
- [Leetcode][JAVA] Triangled
- Java Hour 31 Weather ( 4 )
- 无责任Windows Azure SDK .NET开发入门篇二[使用Azure AD 进行身份验证--2.1使用Azure AD需要了解几个概念]
- phpcms(4) V9 栏目管理
- Qt入门(7)——窗口几何结构
- SDL音频播放
- java collection framework
- 【Sort】Merge Sort归并排序
- 手把手教小白如何用css+js实现页面中图片放大展示效果
- 页面引入css用link和import的区别
- riot.js教程【五】标签嵌套、命名元素、事件、标签条件
- vue 中 vue-router、transition、keep-alive 怎么结合使用?
- 典型分布式系统分析:Bigtable
- Android assets的一个bug
- OpenCV-Python入门教程4-颜色空间转换
- 20165327 2017-2018-2 《Java程序设计》第6周学习总结
- POJ 1265 pick定理
热门文章
- springboot(一) 热部署
- 源码阅读之LinkedList(JDK8)
- 指向“”的 script 加载失败
- $CF19A\ World\ Football\ Cup$
- &#39;latin-1&#39; codec can&#39;t encode characters in position解决字符问题
- 转 DOS(CMD)下批处理换行问题/命令行参数换行 arg ms-dos
- Tuple类型的使用
- headroom.js使用
- npm install的时候报错 npm err code 1
- 华硕(ASUS)X554LP笔记本在64位win7下无线网络连接问题