AT_ddcc_2016_qual_d 道路網
题目描述
有一个由 $N$ 个城市和 $N-1$ 条道路组成的国家。每个城市编号为 $1,\,2,\,\ldots,\,N$。第 $i$ 条道路（$1\leq i\leq N-1$）连接城市 $A_i$ 和城市 $B_i$，长度为 $C_i$。道路是双向通行的，任意两个城市之间都可以通过若干条道路互相到达。
有一天，对于所有满足 $1\leq i
输入格式
输入通过标准输入按以下格式给出。
> $N$ $X$ $A_1$ $B_1$ $C_1$ $\ldots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$
输出格式
请输出答案，输出一行。
说明/提示
## 限制条件
- $2\leq N\leq 10^{5}$
- $1\leq A_i,\,B_i\leq N\ (1\leq i\leq N-1)$
- $1\leq C_i\leq 10^{5}\ (1\leq i\leq N-1)$
- $1\leq X\leq 10^5$
- 在操作进行之前，任意两个城市之间都可以通过若干条道路互相到达
- $C_i,\,X$ 均为整数
## 样例说明 1
下图表示城市和道路的关系。蓝色实线表示原有的 $N-1$ 条道路，黑色虚线表示操作后新增的长度为 $3$ 的道路。
由 ChatGPT 4.1 翻译