树上移动问题

题目描述

小杨有一棵包含 n 个节点的树，每个节点被标记为白色（0）或黑色（1）。小杨可以选择任意节点 s 和 t，从 s 出发移动到 t，要求路径不重复经过节点且最多经过 k 个黑色节点。目标是找到满足条件的路径中经过的最多节点数。

输入格式

• 第一行：n（节点数），k（最大允许黑色节点数）
• 第二行：n 个整数 a1..an（0 或 1，表示节点颜色）
• 接下来 n-1 行：每行 u, v，表示树的一条边

输出格式

一个整数，表示最多经过的节点数。

样例

输入

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

输出

3