CF1709E XOR Tree

题目描述

给定一棵包含 $n$ 个顶点的树，每个顶点 $i$ 上写有一个正整数 $a_i$。

一条简单路径指不重复经过顶点的路径。路径的权值定义为路径上所有顶点权值的按位异或。

称一棵树是好的，当且仅当树中不存在权值为 $0$ 的简单路径。你可以进行任意次操作，每次选择一个顶点，并将该顶点上的权值替换为任意正整数。

请问最少需要进行多少次操作，才能使整棵树变为好的。

输入格式

第一行一个整数 $n$，表示顶点数。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个顶点的权值。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示树中的一条无向边。

输出格式

输出一行一个整数，表示最少操作次数。

样例

样例输入

3
1 2 3
1 2
2 3

样例输出

1

数据范围与约定

$1\le n\le 2\times 10^5$，$1\le a_i<2^{30}$，$1\le x,y\le n$，输入边构成一棵树。