logo AlgoBeat OnlineJudge
登录 注册

#213994. [蓝桥杯 2024 省研究生组] 植物生命力

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小蓝是一位资深的植物学家。他专注于研究植物的相互关系和生命力。在他所照料的森林中,每个品种的植物都拥有独特的生命力,彼此之间互不相同。

植物的生命力会影响其下级品种的生长。具体地,如果下级品种的生命力数值无法被上级品种的生命力数值整除,或者下级品种的生命力数值大于上级品种的生命力数值时,它们便会受到压制,无法茁壮成长。

为了深入研究和定量分析这一现象,小蓝构建了一种模型。他将森林中的植物品种关系抽象成了一棵包含 个结点的树,结点的编号从 1 到 ,代表不同的植物品种。其中,树的根结点编号为 ,结点 )的生命力表示为

现在,小蓝想要对于每个结点 ,统计其子树(以 为根的子树)中同时满足以下两个条件的子结点的数量:

  1. 子结点的生命力小于结点 的生命力
  2. 结点 的生命力 无法被子结点的生命力整除。

请你帮助小蓝计算出所有子树中满足条件的结点个数的总和。

输入格式

输入的第一行包含两个整数 ,分别表示结点的数量和根结点的编号。

第二行包含 个互不相同的整数 ,相邻整数之间使用一个空格分隔,其中 表示编号为 的结点的生命力。

接下来的 行,每行包含两个整数 ,用一个空格分隔,表示编号为 的结点之间存在一条边。

输出格式

输出一行包含一个整数,表示所有子树中满足条件的结点个数的总和。

样例

样例输入 1

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

样例输出 1

4

数据范围与提示

【样例说明】

在给定的样例中,树的结构如下:

    1
   / \
  2   3
 / \   \
4  5    6

在以 为根的子树中,满足条件的结点有 ,个数为

在以 为根的子树中,满足条件的结点有 ,个数为

在以 为根的子树中,没有满足条件的结点,个数均为

因此答案为

【评测用例规模与约定】

对于 的评测用例, 互不相同。

对于所有评测用例, 互不相同。