首页 > 试题广场 >

求和

[编程题]求和

已知有  个节点，有  条边，形成一个树的结构。

给定一个根节点 ，每个节点都有一个权值，节点i的权值为 。

给  个操作，操作有两种类型：

1 a x ：表示将节点  的权值加上 

2 a ：表示求  节点的子树上所有节点的和（包括  节点本身）


输入描述:
第一行给出三个正整数 ，表示树的节点数、操作次数、和这棵树的根节点.
第二行给出  个正整数，第  个正整数表示第  个节点的权值 
下面  行每行两个正整数 ，表示边的两个端点
接下来  行，每行给出一个操作


输出描述:
对于每个类型为 2 的操作,输出一行一个正整数,表示以  为根的子树的所有节点的权值和
示例1

输入

5 6 1
1 2 3 4 5
1 3
1 2
2 4
2 5
1 2 10
1 3 10
1 4 5
1 5 1
2 3
2 2

输出

13
27

备注:



建议使用 scanf 读入
算法知识视频讲解
开通博客
头像 Kur1su
发表于 2020-04-19 09:41:27
Solution 比较经典的题型了吧, 我的做法是dfs序 + 树状数组因为题目要求我们做到单点修改, 区间求和的一个操作显然树状数组能够满足要求那么问题便转化为如何把树上问题转化为简单的区间问题考虑到每一个子树在dfs序下一定是连续的我们可以保存它的编号最小点和编号最大点, 用来表示它的子树比如, 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 sunsetcolors
发表于 2020-04-18 22:31:31
牛客小白月赛24 I 求和 题目地址： https://ac.nowcoder.com/acm/contest/5158/I 基本思路： 来晚了,随便挑了一题I写,由于自己过于***树状数组写错了,所以没在比赛结束前交上去。这题总体来说还是比较裸的,我们求一下dfs序,然后用树状数组维护子 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 子希
发表于 2020-11-09 23:00:07
思路：最朴素的做法：维护一个dp[i]:以i为子树的所有结点和，然后对于每个节点更新，朴素的更新它父亲节点的值，但是，如果树是一个长链这个就超时了。正解：先dfs求一个dfs序，这样以i节点的子树都是在一段区间内，所以我们可以维护一下i的子树的数量，那么求以i为根的子树和就是[dfs(i) - 1, 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 lifehappy
发表于 2020-11-07 17:21:52
求和 利用dfs序在子树上的连续性，然后通过单点修改，区间查询即可，这点只要用一颗树状数组即可完成。 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; typedef long long 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-11-07 19:58:33
传送门 使用数组表示当前子树内,深度字母为的有多少个 那么可以开始,这样与有关的所有询问都可以快速得出解 差不多就是板子了 储存询问用或链式前向星 #include <bits/stdc++.h> using namespace std; const int maxn = 5e5+19; 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 林思艺
发表于 2020-11-10 19:15:20
题意 给你一颗以 为根有 个节点的树，每个节点有一个点权。给你 次操作 ，操作有两种类型： 表示将节点 的权值加上 ； 表示求以 为根的子树上所有节点的和（包括 节点）； 分析 我们可以通过 序将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。直 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Kur1su
发表于 2020-11-09 09:27:31
Description Solution 以前牛客小白赛里也有类似的题目，简单地讲，在树上进行子树区间上的修改和求和问题可以转化为我们熟悉的序列问题。思路：处理出dfs序，然后找到每个节点的子树区间在哪个访问内，剩下的就是树状数组单点修改，区间求和的操作啦。时间复杂度：O(nlogn) Code 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Ke2sen
发表于 2020-04-19 07:15:36
显然这就是一个树链剖分板子题 code #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #includ 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-11-09 10:23:46
Solution #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__v 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 rk_no
发表于 2020-11-07 17:28:05
题目： 给一棵以为根的有根树，点权 。个操作，操作有两种类型：：表示将节点的权值加上；：表示求节点的子树上所有节点的和（包括结点本身）； 做法： 单点修改，求子树上的点权和。我们通过序可以将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。线段树或树状数组就行了。 代 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

难度：
0条回答 1浏览

热门推荐

相关试题

求和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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