题解

题面描述

给定一棵有 $n$ 个节点的树，每个节点 $i$ 具有权值 $a_i$。定义一条路径的权值为这条路径上所有节点权值的 $gcd(a_{b_1},a_{b_2},\dots,a_{b_h})$，其中路径上的节点编号为 $b_1,b_2,\dots,b_h$。当路径只有一个节点时，其路径权值即为该节点的权值。要求统计树中有多少条简单路径的权值为偶数。注意：我们认为 $u\to v$ 和 $v\to u$ 是同一条路径，且 $u\to u$ 也算一条路径。

思路

本题的核心在于利用最大公约数为偶数的充要条件，即路径上所有节点必须均为偶数，将原问题转化为仅考虑偶数节点构成的子图，然后在该子图中寻找各个连通块，对于每个连通块中包含的偶数节点数记为 $k$，简单路径数为 $\frac{k(k+1)}{2}$，最后将所有连通块的路径数累加得到答案。

题目内容

对于一条路径的权值为$gcd(a_{b_1},a_{b_2},$$a_{b_3},...,a_{b_h})$，其中$b1, b2, b3,...,b_k$是路径上的节点编号，当路径上只有一个点路径权值即为该点的点权。

请你统计树中有多少条简单路径的权值为偶数。

我们认为$u→v$和$v →u$ 是同一条路径。特别的，我们认为$u→u$也是一条路径

输入描述

第一行一个整数$n(1≤n≤2×10^5)$，表示树的结点总数。

第二行$n$个整数，第$i$个为$a_i(1≤a_i≤10^6)$,表示结点的权值。

接下来$n -1$行，每行两个整数$u,v(1≤u,v≤n;u≠v)$,表示结点$u$和结点$v$之间通过一条无向边连接。

输出描述

一个整数，表示有多少条简单路径的权值为偶数。

样例1

输入

4
12 16 3 4
1 2
1 3
2 4

输出

6