首页 > 试题广场 >

华华和月月种树

[编程题]华华和月月种树
华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。
华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：
操作 1：输入格式，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。
操作 2：输入格式 ，表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。
但是月月有时会检查华华有没有认真维护这棵树，会作出询问：
询问 3：输入格式，华华需要给出 i 节点此时的权值。
华华当然有认真种树了，不过还是希望能写个程序以备不时之需。

输入描述:
第一行一个正整数M，接下来M行，每行先输入一个正整数O表示操作类型，再输入一个非负整数i表示操作或询问的节点编号，如果O=2，再输入一个正整数a。


输出描述:
对于每个询问3，输出一个非负整数表示询问的答案。
示例1

输入

9
1 0
2 0 1
3 0
3 1
1 0
1 1
2 0 2
3 1
3 3

输出

1
1
3
2

备注:
，保证操作1的数量不超过，保证操作2中的参数a满足
算法知识视频讲解
开通博客
头像 Kur1su
发表于 2020-08-19 22:28:11
Description 华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：操作 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 sunsetcolors
发表于 2020-08-19 16:34:01
华华和月月种树 题目地址： https://ac.nowcoder.com/acm/problem/23051 基本思路： 我们考虑先离线,将树建出来,然后在序上用差分树状数组维护,但是在这样做的过程中,对于每次的操作二,有些实际还没有被加入的点也被算了权值,所以我们在每次新加点的时候记录一 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-08-21 10:34:18
题意：一开始被给予一棵只有一个编号为0、权值为0的根节点的树，有M个操作，每个操作为以下三种之一：操作1：输入格式为1 i 表示给i节点加个权值为0的子节点，编号为当前最大编号+1。操作2：输入格式为2 i a 表示给i为根的子树所有节点的权值加a。操作3：输入格式为3 i 表示输出i节点的权值。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zzugzx
发表于 2020-08-19 15:19:05
题目链接 题意：题解：AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #def 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 lifehappy
发表于 2020-08-19 16:25:25
华华和月月种树 思路 树上对整颗子树进行操作，容易想到用序，但是这是一颗动态变化的树，所以我们可以考虑离线操作。 既然是离线操作，那就简单了，先存下一整棵树以及所有的操作，然后按照要求模拟即可： 对于操作二我们直接以最终一整颗树中形态来进行差分。 对于操作一这里就有有一个关键点了，这个时候刚好有一 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-08-19 16:33:48
参考题解 题目意思 第一行一个T，代表总操作数T，T<4e5后面有T行，分三种情况。第一个数是1，生成一个新的节点挂在第二个数的子节点位置，编号为第几次操作1就是几。第二种情况是第一个数为2，把第二个数以及全部子树权值都增加第三个数大小。第三种情况是第一个数是3，直接输出第二个数的权值。 So 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-08-19 18:05:32
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; vector<int>vec[maxn]; int sumn[maxn],m; int top=1,idmin[maxn],idmax[m 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2020-08-20 12:12:21
题意：华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：操作 1：输入格式1 i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 luo想要个气球
发表于 2020-08-20 15:26:53
题意： 思路： 离线操作，把所有操作存起来，对于所有1操作建好一颗最终的树就变成了裸的树链剖分但是可能会出现，一个点还没建出来就已经被加了权值的错误因此对于每一个操作1就将新建的点的权值归零 #include <cstdio> #include <algorithm> #i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Z_L_G
发表于 2025-08-18 15:24:59
题意 m个操作，起始只有结点0，有如下三种操作 1 i——在结点i下开一个新点，序号为最大编号 2 i a——给结点i的子树全部加上a 3 i——查询结点i的值 思路 先把操作记录下来，建出树 对整颗子树的操作其实就是对dfn的一段区间操作，所以，所有的操作都可以在按dfn顺序的线段树上 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

思维题
难度：
0条回答 17浏览

热门推荐

相关试题

华华和月月种树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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