Solution 比较经典的题型了吧, 我的做法是dfs序 + 树状数组因为题目要求我们做到单点修改, 区间求和的一个操作显然树状数组能够满足要求那么问题便转化为如何把树上问题转化为简单的区间问题考虑到每一个子树在dfs序下一定是连续的我们可以保存它的编号最小点和编号最大点, 用来表示它的子树比如,
展开全文
牛客小白月赛24 I 求和 题目地址： https://ac.nowcoder.com/acm/contest/5158/I 基本思路： 来晚了,随便挑了一题I写,由于自己过于***树状数组写错了,所以没在比赛结束前交上去。这题总体来说还是比较裸的,我们求一下dfs序,然后用树状数组维护子
展开全文
思路：最朴素的做法：维护一个dp[i]:以i为子树的所有结点和，然后对于每个节点更新，朴素的更新它父亲节点的值，但是，如果树是一个长链这个就超时了。正解：先dfs求一个dfs序，这样以i节点的子树都是在一段区间内，所以我们可以维护一下i的子树的数量，那么求以i为根的子树和就是[dfs(i) - 1,
展开全文
求和 利用dfs序在子树上的连续性，然后通过单点修改，区间查询即可，这点只要用一颗树状数组即可完成。 /*
Author : lifehappy
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long
展开全文
传送门 使用数组表示当前子树内,深度字母为的有多少个 那么可以开始,这样与有关的所有询问都可以快速得出解 差不多就是板子了 储存询问用或链式前向星 #include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+19;
展开全文
题意 给你一颗以 为根有 个节点的树，每个节点有一个点权。给你 次操作 ，操作有两种类型： 表示将节点 的权值加上 ； 表示求以 为根的子树上所有节点的和（包括 节点）； 分析 我们可以通过 序将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。直
展开全文
Description Solution 以前牛客小白赛里也有类似的题目，简单地讲，在树上进行子树区间上的修改和求和问题可以转化为我们熟悉的序列问题。思路：处理出dfs序，然后找到每个节点的子树区间在哪个访问内，剩下的就是树状数组单点修改，区间求和的操作啦。时间复杂度：O(nlogn) Code
展开全文
显然这就是一个树链剖分板子题 code #include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#includ
展开全文
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
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
