http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1486. 树(王康宁)
时间限制:1.0s   内存限制:512.0MB  
总提交次数:475   AC次数:106   平均分:53.60
将本题分享到:
   
 
问题描述
  给出一棵N个点的树,每个点有各自的权值,小A想选出一条简单路径,使得这条路径上的点的权值的异或和最大。另外,小A有一些喜欢的点,他希望在这条路径上经过至少K个自己喜欢的点。
输入格式
  第一行包括两个整数N, K,分别表示树的点数和路径上至少包含的小A喜欢的点的数量。
  接下来一行N个整数,每个数均为0或1,小A喜欢第i个点当且仅当这一行的第i个数是1。
  接下来一行N个整数V1, V2, …, VN,其中第i个数表示第i个点的权值。
  最后N-1行,每行两个整数u, v,表示树的一条边。
输出格式
  如果不存在这样的简单路径,输出-1。否则输出最大的异或和。
样例输入
3 1
1 1 1
0 4 7
1 2
2 3
样例输出
7
样例输入
3 2
1 0 1
3 5 6
1 2
2 3
样例输出
0
样例输入
4 4
1 1 1 1
10 10 10 10
1 2
1 3
1 4
样例输出
-1
数据规模和约定
测试点标号
N的范围
K的范围
Vi的范围
其它特点
1
N=2
K=0


2
N≤10



3
N≤1000


这棵树是一条链
4
N≤1000
K=0

这棵树是一条链
5
N≤4000



6
N≤30000
K=0
Vi≤7

7
N≤40000
K=0


8
N≤40000
K=0


9
N≤50000
K=0

这棵树是一条链
10
N≤50000
K=0


11
N≤60000

Vi≤7

12
N≤60000


这棵树是一条链
13
N≤70000

Vi≤107

14
N≤70000

Vi≤107

15
N≤80000



16
N≤80000



17
N≤90000



18
N≤90000



19
N≤100000



20
N≤100000



  对于100%的数据,1≤N≤100000, 0≤K≤N, 0≤Vi≤109, 保证输入的是一棵合法的树.