E-三叶草_牛客练习赛130

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一棵 $n$ 个节点的无根树，每个节点都有一种颜色 $col_i$ （黑或者白）。

若存在 $a,b,c,d$ 这 $4$ 个不同的节点满足 $col_b=col_c=col_d$ ， $col_a\not=col_b$ ，且 $a$ 与 $b,c,d$ 均有邻边，则称 $a,b,c,d$ 构成了一片三叶草。

你至多有 $k$ 次修改，每次修改可以改变一个节点的颜色（黑 $\to$ 白或者白 $\to$ 黑），请问树上最多可以构成多少片三叶草。

第一行输入  个整数 ，分别表示树的大小，最多修改的次数。

第二行输入  个数 ，表示每个节点的颜色（ 表示白色， 表示黑色）。

接下来  行，每行输入两个正整数 ，表示  与  之间有一条边。

请你输出树上最多可以构成多少片三叶草。

示例1

复制

复制

可以把  改为 ，这样  构成了一片三叶草。

示例2

复制

8 2
1 0 1 0 0 0 0 1
1 2
1 3
1 4
1 5
3 6
4 7
4 8

复制


一种能使得三叶草数量达到最大值的操作方式如下：
改变  节点的颜色，最终树上的三叶草有：，，，，，一共  个。