#P9788. 搞搞新意思
搞搞新意思
题目描述
给定一棵有 个点的无向树,边权为非负整数。两点距离是它们之间路径上的边权之和,树的直径是所有两点距离的最大值。
对于每个询问给出的整数 ,你可以选择一条边,把它的权值改成 ,也可以不修改任何边。求这样能得到的最小直径。
每个询问独立处理,下一次询问开始前恢复原图。
输入格式
第一行一个整数 。接下来 行,每行三个整数 ,表示连接 的边原权值为 。
接下来一行一个整数 。其后 行,每行一个整数 ,表示一次询问。
输出格式
输出 行,每行一个整数,表示对应询问能得到的最小直径。
样例
7
1 2 5
2 3 4
2 4 4
4 5 3
5 6 3
6 7 3
1
2
16
原赛样例 2 见下发文件。
数据范围
,。原题未给原边权 的独立数值上限。
- 对于 的数据,。
- 对于 的数据,。
- 另有 的数据, 且 。