#1892. [GESP202412 八级] 树上移动

[GESP202412 八级] 树上移动

题目描述

小杨有一棵包含 nn 个节点的树,其中节点的编号从 11 到 nn,每个节点的颜色要么是白色要么是黑色,小杨可以任意选择节点 ss 和节点 tt 并从节点 ss 出发移动到节点 tt,移动过程中小杨不能够经过重复节点。

小杨希望自己在至多经过 kk 个黑色节点的前提下,经过的总节点数尽可能多,请你帮小杨选择经过最多的节点数是多少。

输入格式

第一行包含两个正整数 n,kn,k,代表节点数量和至多经过的黑色节点数。

第二行包含 nn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_n,代表节点颜色,如果 ai=0a_i=0,代表节点颜色为白色,如果 ai=1a_i=1,代表节点颜色为黑色。

之后 n−1n-1 行,每行包含两个正整数 ui,viu_i,v_i,代表存在一条连接 uiu_i 和 viv_i 的边。

输出格式

输出一个正整数,代表最多经过的节点数。

样例

5 1
0 0 1 1 1
1 2
2 3
2 5
1 4
3

题目来源:洛谷 P11379