首页 > 试题广场 >

路径积

[编程题]路径积
  • 热度指数：198 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一棵n个节点的无根树(n个结点，n-1条边的无环连通图)，每个节点有一个权值a_i

一共有m次查询，每次查询x_i到y_i的最短路径上所有点权的乘积。

为了防止答案过大，答案对1e9+7取模。


示例1

输入

6,2,[1,2,3,4,5,6],[1,2,2,4,4],[2,3,4,5,6],[3,6],[5,5]

输出

[120,120]

说明

3到5的最短路径为3->2->4->5，路径积为3*2*4*5=120
6到5的最短路径为6->4->5，路径积为6*4*5=120

备注:


第一个参数n代表节点个数
第二个参数m代表查询次数
第三个参数vector a代表每个节点的权值
第四、五个参数vector u,v各自包含n-1个元素代表树上的边，u_i与v_i相连
第六、七个参数vector x,y各自包含m个元素，代表查询x_i到y_i的最短路径上的点权乘积

对于每个查询，答案存储在vector中并按照查询的时间顺序输出
算法知识视频讲解
添加回答
Scarecrow928头像 Scarecrow928

预处理：

  1. 邻接表
  2. 假设第1个节点为root，dfs计算出所有节点到root节点的路径积products，形成前缀积树，同时保存root到所有节点经过的节点为path。

寻找两个结点的LCA：遍历root到两个节点的路径，公共祖先不同时停止循环

求路径积：已知节点x, y, 它们的最近公共祖先lca，路径积products，各节点权值a，公式为：
路径积

模1e9+7求-2次幂等于求乘法逆元 ，可以用扩展欧几里得算法

编辑于 2021-08-20 13:28:57 回复(0)
zlc1114头像 zlc1114
可以直接裸LCA随便做下；如果除的不是质数无法使用逆元则可以倍增LCA的同时随便维护一下
树上莫队复杂度也能都接受
发表于 2021-03-22 17:16:05 回复(0)
提交观点

问题信息

队列 树
难度：
2条回答 1757浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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