4492: 「CEOI2017」Chase

在逃亡者的面前有一个迷宫，这个迷宫由 $n$ 个房间和 $n-1$ 条双向走廊构成，每条走廊会链接不同的两个房间，所有的房间都可以通过走廊互相到达。换句话说，这是一棵树。 逃亡者会选择一个房间进入迷宫，走过若干条走廊并走出迷宫，但他永远不会走重复的走廊。 在第 $i$ 个房间里，有 $F_i$ 个铁球，每当一个人经过这个房间时，他就会受到铁球的阻挡。逃亡者手里有 $V$ 个磁铁，当他到达一个房间时，他可以选择丢下一个磁铁（也可以不丢），将与这个房间相邻的所有房间里的铁球吸引到这个房间。这个过程如下： 1. 逃亡者进入房间。 2. 逃亡者丢下磁铁。 3. 逃亡者走出房间。 4. 铁球被吸引到这个房间。 注意逃亡者只会受到这个房间原有的铁球的阻拦，而不会受到被吸引的铁球的阻挡。 在逃亡者走出迷宫后，追逐者将会沿着逃亡者走过的路径穿过迷宫，他会碰到这条路径上所有的铁球。 请帮助逃亡者选择一条路径，使得追逐者遇到的铁球数量减去逃亡者遇到的铁球数量最大化。

第一行两个空格隔开的整数整数 $n$ 和 $V$。 第二行 $n$ 个空格隔开的整数表示 $F_i$。 之后的 $n-1$ 行，每行两个空格隔开的整数 $x$ 和 $y$，表示有一条走廊连接编号为 $x$ 和编号为 $y$ 的房间。

输出一个整数表示最优情况下追逐者遇到的铁球数量减去逃亡者遇到的铁球数量。

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

36