题目内容

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

题解

题面描述

给定一棵有 $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}$，最后将所有连通块的路径数累加得到答案。