题意： 给你一棵 个节点的无根树，每个节点有一个权值，给你 次询问，每次询问你需要求出点 到点 之间的简单路径所经过的点的权值积，答案对 取模。 方法一（暴力求解） 对于每次询问，我们可以把点 和点 都跳到它们的最近公共祖先上，然后把经过的点的权值作为贡献乘到答案里。接下来是如何跳到最近公共祖先上？
展开全文
C题 路径积 有个比较笨的方法 以1为根节点dfs整棵树，把每个节点的深度记录下来（deep[]）,并记录每个节点的父节点（pre[]） 然后，对于(x,y),依据deep[]和pre[],可以向上找到x,y第一个公共的父节点root。路径积就是x->root->y，再向上找公共父节
展开全文
题解 | NC610路径积 题意分析 这道题没有故事背景，直接给出了数学模型，一棵个节点的无根树（个节点，条边的无环连通图），每个节点有一个权值。 询问比较特殊，一共有次查询，每一次是让求从点到点的最短路径上的所有点权的乘积（对取模）。 其实很多人看到最短路径就准备直接Floyd算法、Dijkst
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
