#P14857. [OOI2026 资格赛]Simple Problem简单题

[OOI2026 资格赛]Simple Problem简单题

题目描述

给定一棵有 nn 个顶点的无向树。每个顶点 vv 上记录了一个非负整数 ava_v,满足 0≤av<2k0 \le a_v < 2^k。

如果一个顶点集合中所有顶点的 aa 值按位或等于 2k−12^k-1,则称这个集合是好的。

一个集合的代价定义为集合中任意两点距离的最大值,其中树上两点距离为它们之间唯一简单路径上的边数。

你需要求出一个好集合的最小代价,或判断不存在好集合。

输入格式

第一行包含两个整数 n,kn,k(2≤n≤1000002 \le n \le 100000,1≤k≤201 \le k \le 20),表示树的顶点数和参数 kk。

第二行包含 nn 个整数 aia_i(0≤ai<2k0 \le a_i < 2^k),表示每个顶点的值。

接下来 n−1n-1 行描述树边。第 ii 行包含两个整数 vi,uiv_i,u_i(1≤vi,ui≤n1 \le v_i,u_i \le n),表示第 ii 条边连接的两个顶点。

输出格式

如果不存在好集合,输出 -1。否则输出一个整数,表示好集合的最小代价。

样例

样例输入 1

5 3
1 2 6 0 4
1 2
2 3
1 4
3 5

样例输出 1

2

样例输入 2

3 3
0 1 2
1 2
2 3

样例输出 2

-1

样例解释

第一个样例中,可以选择顶点集合 {1,2,3}\{1,2,3\}。

第二个样例中,能够得到的最大按位或值为 33,无法达到 23−1=72^3-1=7。

计分方式

测试数据包含九个测试组。只有当某组所有测试点以及该组要求的若干前置组均通过时,才能获得该组分数。注意,某些测试组不要求通过样例测试。离线测试表示该组测试结果会在比赛结束后才可见。

组别 分数 nn kk 前置组 备注
0 - - - 样例
1 12 n≤15n \le 15 0 -
2 9 n≤1000n \le 1000 - vi=i,ui=i+1v_i=i, u_i=i+1
3 14 - 2
4 6 k=1k=1 - -
5 10 n≤1000n \le 1000 k=2k=2
6 12 - 5
7 9 n≤100n \le 100 k≤5k \le 5 0
8 16 n≤1000n \le 1000 - 0-2, 5, 7
9 12 - 0-8 离线测试