bzoj#P3935. Rbtree

Rbtree

题目描述

给定一颗 NN 个点的树,树上的每个点或者是红色,或者是黑色。 每个单位时间内,你可以任选两个点,交换它们的颜色。 出于某种恶趣味,你希望用最少的时间调整结点的颜色,使得对于每个点,离它最近的黑色点与它的距离不超过 xx

输入格式

输入的第一行包含整数 NNxx。 接下来一行 NN 个整数 C1,C2,,CNC_1,C_2,\cdots,C_N,表示结点的初始颜色。11 表示黑色,00 表示红色。 接下来 N1N-1 行,每行 33 个整数 ui,vi,wiu_i, v_i,w_i,表示点 uiu_iviv_i 之间存在权值为 wiw_i 的边。

输出格式

输出一个数表示答案;如果无解,输出 1-1

3 2
1 0 0
1 2 2
2 3 2
1

数据规模和约定

对于 100%100\% 的数据,1N5001\le N\le 5001x,wi1091\le x,w_i\le 10^9Ci{0,1}C_i\in\{0,1\}