题解 | #货物收集#

这道题可以使用二分法+DFS来解决。可以二分答案 $midmid$，表示 Venn 最少需要多少武力值才能收集到至少 $WW$ 个货物。

具体做法是，我们首先遍历整棵树，计算出每个点向下子树（不包括父亲节点）的货物储备之和。然后从根节点开始 DFS，维护一个父节点$fafa$表示当前已经经过的点，以及当前点向下子树的货物储备之和$retret$。

在 DFS 的过程中，如果当前点 $a[u-1]a[u-1]$ 的货物储备之和 $s_{u}s\_u$ 加上之前遍历的所有点的货物储备之和 ${\sum }_{(v,w)\in S}w\backslash sum\_\{(v,\; w)\; \backslash in\; S\}\; w$ 大于等于 $WW$，则说明 Venn 可以在 $midmid$ 武力值内收集到至少 $WW$ 个货物，可以将二分的答案上界调整为 $mid-1mid-1$。否则，则说明 Venn 不能在 $midmid$ 武力值内收集到至少 $WW$ 个货物，需要将二分的答案下界调整为 $mid+1mid+1$。

最终，当二分的答案下界和上界相等时，这个值就是 Venn 最少需要的武力值。

n, W = map(int, input().split())
a = [0] + list(map(int, input().split()))

g = [[] for _ in range(n+1)]
# 构建树
for i in range(n-1):
    u, v, w = map(int, input().split())
    g[u].append((v, w))
    g[v].append((u, w))
    
def dfs(u, fa, maxw): # 假设不存在环
    cnt = 0
    for v, w in g[u]: # 遍历子节点
        if v == fa:
            continue
        if w <= maxw:
            cnt += a[v-1]
            cnt += dfs(v, u, maxw)
        else:
            continue
    return cnt

l, r = 0, 1000000000
while l <= r:
    mid = l + (r-l) // 2
    if dfs(1, 0, mid) >= W:
        r = mid - 1
    else:
        l = mid + 1
print(l)