题意 给你一棵 个结点的树, 以 为根。每个结点有点权。有 次操作： 结点权值 ， 的儿子权值 ， 的孙子们 ，以此类推。 询问 的点权； 思路 又是单点查询，看看树状数组吧。区间修改就可以用差分。但是第一个操作有些麻烦，但这和每个节点的深度奇偶有关。所以只需判断一下深度，决定修改的值
展开全文
题目大意：给你一颗树，你可以在树上进行两种操作1 x val,把val加到x节点上面去，然后-val加到x的第一层儿子节点，然后-(-val)加到第二层儿子节点，。。。等2 x,查询x节点的值。思路：这题看了大佬的思路才做出来的。 https://blog.nowcoder.net/n/d8f8d
展开全文
题目： 给你一棵个结点的有根树，为根。结点有点权。个操作：：结点权值，的儿子们权值，的孙子们...以此类推；：询问当前的点权； 做法： 序：从根出发经过结点的顺序，每个结点只加一次，长度。欧拉序：从根出发绕回根沿途经过的结点的顺序，每进入结点加一次，长度。这题的更新操作中，我们发现其在欧拉序中是有
展开全文
Description 给定一棵树，根节点为1，给出两种操作： 查询x节点当前的val 给出x, val, 修改x节点及其子树的值，注意修改过程是随着深度+-+-进行交替的 Solution 首先处理出dfs序，随后单点查询，区间修改可以用差分树状数组来维护。注意到区间修改的过程是随着深度而改变
展开全文
分析 我们发现题目中需要更改的val只跟深度的奇偶又关系并且每次更改会影响到的一段dfn区间内的点所以我们可以用两棵树状数组维护奇数和偶数深度的增量然后就是区间加和单点查询了时间复杂度：期望得分：100分 代码 //CF383C
#include <algorithm>
#include
展开全文
Propagating tree 题目地址： https://ac.nowcoder.com/acm/problem/110318 基本思路: 我们发现是非常裸的子树修改然后单点查询,所以我们考虑用差分树状数组去维护子树状态,但是我们发现它对于权值的修改是一层加一层减这样的,所以一个树状数组
展开全文
题意：给你一棵n个结点的树, 以1为根。每个结点有点权。有m次操作：1.x结点权值 +val，x的儿子权值 −val，x的孙子们 +val，以此类推。2.询问x的点权；题解：我们首先跑一边dfs序，顺便求除每个结点的深度。我们把他分成两颗线段树，深度为奇数的在第一颗上，深度为偶数的在第二课上。我们每
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
