#P8675. [2019年省队联测]睡眠

    ID: 8762 传统题 1000ms 512MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>数据结构图论CF2500分治字典树状压DP树形DP

[2019年省队联测]睡眠

如果每天晚上要靠数羊才能睡着,那我推荐你最好去练练养老太极拳来缓解压力

Description

AKMer觉得,人生其实是一棵树,从根开始,没有回头路,由一道又一道选择题组成。有的人活得很长但是碌碌无为,那是因为他选择了长度较长但是权值很小的一条路。有的人燃烧青春成为别人眼中耀眼的光,那是因为选择了长度较短但是权值很大的一条路。

一条路的权值是这条路径上所有点的权值的异或和。为什么是异或和?因为阴阳均衡(0(阴)xor 1(阳)=1(真))才是至道,所以异或是最完美的运算。

AKMer在入坑OI之后发现原来自己做错选择题了,可惜这是树不是图,没有后悔路、返祖边。NOIP2018完挂的他觉得自己省选也没有什么希望,只有1e-2511154%的几率进队。所以他觉得人生很迷惘,很幻灭。感到迷惘的人往往连写出来的题面都显得很罗嗦。

如果有来生,AKMer想,我一定要做正确的选择。

由于AKMer对于省选已经不抱有任何希望了,所以他决定拿他仅有的1e-2511154%的进队几率与你交换Black Sheep Wall这句言灵,希望你告诉他来世应该怎么选择才能既活的长又能很舒服。

由于你是魔鬼,你能看见AKMer来世的人生树,点有点权,而且有的点是重要点,重要点代表的是人生中不发生个若干次都不敢说自己活过的事情,比如穿女装Cos服参加省选、将多校联测的题面当作是艺术品来书写然后遭人怒骂或者是用五个月时间增长自己的实力去挑战Wolfycz Alex Honnold。AKMer觉得人来这世界走一遭就是来体验的,至少要经历k次这样的事件人生才算圆满,所以他想问问你这棵树上经过至少k个重要点的路径的权值最大值是多少。

哦对了,AKMer想起来他似乎忘记告诉你一件很重要的事情了,那就是你找的这条路径还需要是“太极”路径。如果不是太极路径,那么下辈子也许他每天晚上都得靠数羊才能睡着了。

树上每条边是黑色或白色的。如果在某一条简单路径上存在一个点,这个点不是路径的端点,并且这个点到两个端点的两条子路径都满足路径上黑色和白色边数相等,那么这条路径就是太极路径。

比如1-2=3-4=5-6-7-8=9=10=11就是太极路径,因为5不是端点,5到1的路径有两条白色的边和两条黑色的边,5到 11有三条白色的边和三条黑色的边。(-是白色的边,=是黑色的边)

因为他跟你交换的东西并不是14\frac{1} {4}的生命而是1e-2511154%的进队几率这种廉价的东西,所以你只需要告诉他这个最大的权值即可。至于究竟该怎么走人生路,还是得要AKMer自己去探索。

Input

第一行包括两个数N,K,表示树上的点数和AKMer要求至少经历人生中不发生个若干次都不敢说自己活过的事情的次数。

第二行N个数,每个数取值为0或1,表示这件事是否算是人生中不发生个若干次都不敢说自己活过的事情。 第三行N个数,valiv a l_{i}表示第 ii 个节点的权值。

接下来N-1行,每行三个数u,v,col表示u,v之间存在一条边,颜色为col,0为黑,1为白。

Output

如果不存在满足上述条件的路径则输出-1,否则输出最大的权值。

样例1输入

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

样例1输出

13

样例1解释

路径 9=5-10=6-1 的权值为13;9=5-10=6-7 的权值为0;9=5-10=6-3 的权值为2。

样例2输入

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

样例2输出

12

样例2解释

路径 6-2=9-4=3 的权值为12;6-2=9-4=5 的权值为5。

Constraint

数据点编号 n= k= 特殊性质
1 251 4 无
2 500 5
3 3141 11
4 4888
5 5000
6 100000 20 树是一条链
7
8 0 所有偶数点都与1相连,除1以外所有奇数点i与i-1相连
9
10 无
11
12 12
13 20
14
15
16
17 17
18 18
19
20