首页 > 试题广场 >

父子情深

[编程题]父子情深

题意

在一颗有 $n$ 个结点且以 $1$ 为根节点树上，起初每个结点的初始权值为 $0$ 。

现在有 $q$ 次操作，每次操作选择将以 $r_i$ 为根节点的子树上的所有结点权值增加 $x_i$ 。

求 $q$ 次操作后从 $1$ 到 $n$ 每个结点的权值。

第一个参数为 $n$ ， $1\leq n \leq 100,000$

第二个参数为边 $(u_i, v_i)$ 的集合，其中 $(u_i, v_i)$ 表示结点 $u_i$ 与结点 $v_i$ 之间有一条边， $1\leq u_i, v_i \leq n$

第三个参数为 $q$ ， $1 \leq q \leq 100,000$

第四个参数为 $q$ 次询问的 $(r_i, v_i)$ 的集合， $1\leq r_i \leq n, 0 \leq \lvert v_i \rvert \leq 1000,000$

从 $1$ 到 $n$ 每个结点的权值。

示例1

5,[(2,5),(5,3),(5,4),(5,1)],2,[(1, 3), (2, -1)]

[3,2,3,3,3]

第一次操作，将以 1 为根节点的子树上的所有结点权值增加 3，此时结点的权值分别为 [3, 3, 3, 3, 3] ；
第二次操作，将以 2 为根节点的子树上的所有结点权值增加 -1，此时结点的权值分别为 [3, 2, 3, 3, 3] ；

算法知识视频讲解

其实是牛哥

这题这么难吗都没人讨论

发表于 2021-09-16 19:26:59 回复(0)

提交观点

树

难度：

1条回答 1收藏 1214浏览

查看代码

扫一扫，把题目装进口袋