#P3935. Rbtree

    ID: 3141 传统题 1000ms 512MiB 尝试: 126 已通过: 56 难度: 8 上传者: 标签>CF2500提高+/省选-树上背包子树转区间子树合并剪除无效容量

Rbtree

题目描述

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

输入格式

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

输出格式

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

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

数据规模和约定

对于 100%100\% 的数据,1≤N≤5001\le N\le 500,1≤x,wi≤1091\le x,w_i\le 10^9,Ci∈{0,1}C_i\in\{0,1\}。