#P9788. 搞搞新意思

    ID: 6417 传统题 1000ms 256MiB 尝试: 40 已通过: 11 难度: 7 上传者: 标签>CF2300提高换根 DP树直径二分查找前后缀最值高精度加法高精度减法

搞搞新意思

题目描述

给定一棵有 nn 个点的无向树,边权为非负整数。两点距离是它们之间路径上的边权之和,树的直径是所有两点距离的最大值。

对于每个询问给出的整数 ww,你可以选择一条边,把它的权值改成 ww,也可以不修改任何边。求这样能得到的最小直径。

每个询问独立处理,下一次询问开始前恢复原图。

输入格式

第一行一个整数 nn。接下来 n−1n-1 行,每行三个整数 u,v,du,v,d,表示连接 u,vu,v 的边原权值为 dd。

接下来一行一个整数 mm。其后 mm 行,每行一个整数 ww,表示一次询问。

输出格式

输出 mm 行,每行一个整数,表示对应询问能得到的最小直径。

样例

7
1 2 5
2 3 4
2 4 4
4 5 3
5 6 3
6 7 3
1
2
16

原赛样例 2 见下发文件。

数据范围

1≤n,m≤1051\le n,m\le10^5,1≤w≤1091\le w\le10^9。原题未给原边权 dd 的独立数值上限。

  • 对于 20%20\% 的数据,n,m≤200n,m\le200。
  • 对于 40%40\% 的数据,n,m≤2000n,m\le2000。
  • 另有 20%20\% 的数据,n≤105n\le10^5 且 m≤10m\le10。

原 PDF 题面