Tree

题号：NC230424
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一棵包含 $n$ 个节点的``宝石树''。除了节点 $1$ 以外，每个节点 $i(i\in[2,n])$ 上都结有价值为 $a_i$ 的宝石，且节点 $u$ 与节点 $v$ 之间的链长为 $d_{uv}$ 。

现在假设小明有个初始体力值 $t$ 。

如果他想从节点 $u$ 经过链 $d_{uv}$ 走到节点 $v$ ，从而获取节点 $v$ 上的宝石，那么需要保证 $t\geq d_{uv}$ ，否则无法通过该条链。注意这里的链是双向的，即如果可以从 $u$ 走到 $v$ ，那也可以从 $v$ 走到 $u$ 。

当到达节点 $v$ 时，小明立马会恢复初始体力值 $t$ ，从而再有可能移动到下个节点。

已知小明一开始站在节点 $1$ 的位置，他需要获取价值总和至少为 $s$ 的宝石，问他的初始体力值 $t$ 最小是多少。

题目保证所有节点宝石价值之和不小于 $s$ ，且每个节点上的宝石最多被摘取一次。

第一行两个正整数 $n,s(2\leq n\leq 10^5,1\leq s\leq 10^9)$ 。

接下来一行，有 $n-1$ 个正整数，第 $i$ 个数字 $a_i$ 表示编号为 $i+1$ 节点上的宝石价值 $(1\leq a_i\leq 10^9)$ 。

接下来 $n-1$ 行，每行有三个正整数 $u,v,d_{uv}$ 。

表示节点 $u,v$ 之间的链长为 $d_{uv}(1\leq u,v\leq n,1\leq d_{uv}\leq 10^9)$ 。

输出最小初始体力值。

示例1

复制

复制


如上图所示：小明可以从节点通过链 走到节点 ，摘取节点 上的宝石 ，然后回退回节点 ，再由节点 通过链走到节点，摘取节点上的宝石 ，总共可以获得价值为 的宝石，满足大于等于  的要求，这时候小明的初始体力值 只要满足等于即可。