首页 > 试题广场 >

小红的树上路径

[编程题]小红的树上路径
  • 热度指数：139 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了一棵树，每个节点有一个点权。她想取一个长度为 2 的路径，将路径上三个节点的权值相乘。小红希望最终三个节点的乘积的因子数量不小于k，请你帮小红求出有多少种选择路径的方案。

输入描述:
第一行输入两个正整数n和k，代表节点的数量、路径乘积的因子限制。
第二行输入n个正整数a_i，代表每个节点的权值。
接下来的n-1行，每行输入两个正整数u,v，代表节点u和节点v有一条边连接。

1\leq n \leq 10^5
1\leq k \leq 10^2
1\leq a_i \leq 100
1\leq u,v \leq n


输出描述:
一个整数，代表符合条件的路径方案数。
示例1

输入

4 8
1 2 3 6
1 2
2 3
3 4

输出

1

说明

取路径 2-3-4，乘积为 36，共有 9 个因子。符合条件。
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 18:02:42
题目链接 小红的树上路径 思路分析 1. 问题建模 题目要求我们寻找一棵树中所有长度为 2 的路径，这些路径由三个节点（我们称之为 u-v-w）组成，并满足特定条件。 路径结构：一条长度为 2 的路径 u-v-w 由一个中心节点 v 和它的两个不同邻居 u、w 构成。 路径唯一性：每一条这样的路径 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树 组合数学 数论
难度：
2条回答 521浏览

热门推荐

相关试题

小红的树上路径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号