#P3090. Coci2009 [podjela]

    ID: 2245 传统题 1000ms 512MiB 尝试: 72 已通过: 30 难度: 7 上传者: 标签>CF2200提高树上背包以值为状态支配关系子树合并剪除无效容量

Coci2009 [podjela]

题目描述

有 nn 个农民,他们住在 nn 个不同的村子里。这 nn 个村子形成一棵树。

每个农民初始时获得 xx 的钱。

每一次操作,一个农民可以从它自己的钱中,取出任意数量的钱,交给某个相邻村子的农民。

对于每个农民给定一个值 viv_i,求最少需要多少次操作,使得每个农民最终拿到的钱大于等于给定的值。

输入格式

第 11 行一个整数 nn。

第 22 行一个整数 xx。

第 33 行 nn 个整数,表示 viv_i。保证所有 viv_i 的和 ≤n×x\le n \times x。

第 44 到 n+2n+2 行每行两个 11 到 nn 的数,表示树上的一条边。边是双向的。

输出格式

一行一个整数,最少需要的操作次数。

6
15
10 20 18 16 6 16
1 4
4 5
4 6
6 2
5 3
5

数据规模与约定

对于 100%100\% 的数据,1≤n≤2×1031\le n\le 2 \times 10^3,0≤x≤1040\le x\le 10^4。