首页 > 试题广场 >

偶数路径2.0

[编程题]偶数路径2.0

热度指数：220 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游获得了一棵包含 $n$ 个节点的树，每个节点上都有一个数字 $a_i$ 。

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

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

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

输入描述:

第一行一个整数 ，表示树的结点总数。

第二行  个整数，第  个为 ，表示结点的权值。

接下来  行，每行两个整数 ，表示结点  和结点  之间通过一条无向边连接。

输出描述:

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

示例1

输入

输出

算法知识视频讲解

丨阿伟丨

发表于 2025-09-11 18:22:56

题目链接偶数路径2.0 题目描述给定一棵个节点的树，每个节点有一个权值。一条简单路径的权值定义为路径上所有节点权值的最大公约数 (GCD)。你需要统计权值为偶数的简单路径有多少条。注意：路径 u -> v 和 v -> u 视为同一条。单个节点自身也算作一条路径。解展开全文

牛客210938800号

发表于 2025-08-21 11:41:42

分析1.gcd：gcd 表示‌最大公约数(Greatest Common Divisor)；均为偶数：如果一组数据的最大公约数为偶数，由于偶数都能被2整除，所以这组数据的都能被2整除，即都是偶数；均是偶数：如果一组数据都是偶数，那么这组数据都能被2整除，即存在公因子2，所以他们的最大公约数也一定是2 展开全文