首页 > 试题广场 >

扩散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个元素，代表u_i与v_i相连
第五、六、七个参数vector x,y,z各自包含m个元素，代表m次污染
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

树
难度：
0条回答 1145浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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