首页 > 试题广场 >

扩散II

[编程题]扩散II

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

牛客大陆一共有n个工厂，有n-1对工厂之间有管道相连，因为工厂之间需要合作，所以这n-1个管道保证任意两个工厂都可以通过管道互相抵达。每根管道的长度都是1.（换言之，n个工厂与n-1根管道组成了无根树）

牛牛发现，从这片大陆开始工业化以来，一共发生了m次污染。每次污染用3个参数 $x_i,y_i,z_i$ 表示在第 $x_i$ 个工厂发生了污染，影响了所有和第 $x_i$ 个工厂的最短距离小于等于 $y_i$ 的工厂，这些被影响的工厂（包括 $x_i$ ）的污染指数都增加了 $z_i$ 。

一开始所有的工厂污染指数为0.

现在牛牛想知道，在发生了这m次污染之后，每个工厂的污染指数是多少。

示例1

输入

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

输出

[3,6,14,7,8]

说明

在1，2，3，4，5分别发生了距离为1的污染，他们的影响为分别为1，2，3，4，5
1发生的污染影响了1，2
2发生的污染影响了1，2，3
3发生的污染影响了2，3，4，5
4发生的污染影响了3，4
5发生的污染影响了3，5
最终五个工厂污染指数为[3,6,14,7,8]

备注:



第一个参数n代表工厂数量
第二个参数m代表污染发生次数
第三、四个参数vector u,v各自包含n-1个元素，代表与相连
第五、六、七个参数vector x,y,z各自包含m个元素，代表m次污染

算法知识视频讲解

未来0116

发表于 2021-08-18 21:06:36

一.题目描述NC570扩散IIn个节点，n-1条边使之连通(两两之间是联通的)，每条边代表距离为1。一共m次污染，每次发生在数组元素x[i]，影响范围是与发生点距离不超过y[i]，影响范围所有节点污染指数增加z[i]，污染指数初始值全部为0，求m次污染发生后，每个节点的污染指数。二.算法(搜索)理解展开全文

摸鱼学大师

发表于 2021-08-16 14:59:04

思路：题目的主要信息： n个节点，n-1条边使之连通，这就是一棵树（注意不一定是二叉树），每条边代表距离为1 一共m次污染，每次发生在数组元素x[i]，影响范围是与发生点距离不超过y[i]（发生点视为距离为0），影响范围所有节点污染指数增加z[i] 污染指数初始值全部为0，求m次污染发生后，每个展开全文