7935: BZOJ3935:Rbtree
Memory Limit:512 MB
Time Limit:10 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
给定一颗 N 个点的树,树上的每个点或者是红色,或者是黑色。 每个单位时间内,你可以任选两个点,交换它们的颜色。 出于某种恶趣味,你希望用最少的时间调整结点的颜色,使得对于每个点,离它最近的黑色点与它的距离不超过 x。
输入格式
输入的第一行包含整数 N 和 x(1 <= x <= 10^9)。 接下来一行 N 个整数 C1-Cn,表示结点的初始颜色。1 表示黑色,0 表示红色。 接下来 N-1 行,每行 3 个整数 ui, vi,wi(1 <= wi <= 10^9),表示点 ui 和 vi 之间存在权值为 wi的边。
输出格式
输出一个数表示答案;如果无解,输出 “-1”。
样例输入
3 2 1 0 0 1 2 2 2 3 2
样例输出
1
提示
数据规模和约定 对于100%的数据 N<=500
题目来源
没有写明来源