题目： 给一棵以为根的有根树，点权 。个操作，操作有两种类型：：表示将节点的权值加上；：表示求节点的子树上所有节点的和（包括结点本身）； 做法： 单点修改，求子树上的点权和。我们通过序可以将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。线段树或树状数组就行了。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl ...

题目： 给一棵无根树。每个点有一个颜色。个操作。：将结点的颜色修改为；：问所有颜色为的结点的生成树大小。(若不存在颜色为的结点输出) 做法： 这题好神奇。可以用序来维护相同颜色结点的生成树。考虑若颜色的只有个结点、，则其生成树大小就是两个结点在原树上的距离，记为。此时，如果加入第个结点，对生成树的贡献能用树上距离算出来：①若在、之间：（有如下2种情况）不在路径上和在路径上。 ②若不在、之间：（有如下2种情况） 以上所有情况对生成树的贡献都是所以我们可以对相同颜色点的集合按序排序维护（用）。每次加点或删点就取出左右相邻的个点计算贡献，若不存在左或右相邻，就用第②种情况，在一边取个点计算贡献，式...

题目： 给一棵树，每个点有一个英文字母。次询问，问子树内所有深度为的点里的字母能否重排成一个回文串。 做法： 处理子树上的询问，不带修改，询问可离线，我们可以考虑用。这是一种统计子树信息的方式，通过调整顺序，保留重儿子中的信息来优化复杂度。在这个题里，我们要做的就是对每棵子树，得到数组，代表这棵子树内深度为的点中，字符出现的次数。因为能否重排成回文串我们只需知道奇数字符的数量，设为，若>1则，否则。所以这题其实是很裸的，我们每次处理出子树的数组，然后就能判断完该子树下的所有询问。 代码： #include <bits/stdc++.h> #define IOS ios::...

题目： 有一棵个节点的二叉树，为根节点，每个节点有一个值。现在要选出尽量多的点。对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小； 做法： 题意转化一下。“右子树中选的点要比左子树中选的点小”反一下就是“左子树中选的点要比右子树中选的点大”，而又有“若选根结点，子树内选的点要比根节点大”。即我们选出的点有如下关系：根右子树左子树。所以要最大化选点的数量，我们只需要后序遍历这棵树得到后序遍历序列，然后跑一个（最长上升子序列）即可。复杂度。 代码： #include <bits/stdc++....

题目： 给你一棵有根树。个询问，输出从为根的子树往下得到的序列中第个数，超出则输出。 做法： 求出树的序。每个询问输出结点在中往后第个数。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl using namespace std; typedef long long ll; const int N = 2e5 + 7; vector<i...

题目： 给一个类似序的序列。（经过一个结点记录一次颜色）。问有多少棵有根树满足（结点子树之间有序）。答案输出。 做法： 设为序列区间对应有根树的方案数，答案即为。转移思路：我们枚举区间对应的有根树里，第一棵子树的区间，设为，则其他子树对应区间。不难发现，合法的转移中，此时有最后加上只有一棵子树的情况：区间或记忆化搜索都能写，个人喜欢写。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " &l...

题目： 给个点。个操作。：和建权值的有向边；：和建权值的有向边； ：和建权值的有向边； 问从点到其他点的最短路。无法到达输出。 做法： 直接建图时间、空间复杂度都太大了。我们需要用线段树维护区间建图。开两棵线段树，自底向上建零边，自顶向下建零边。如下图：当我们处理这种情况时，只需用和线段树中的某些段点建边。处理时，就是线段树中某些段点和建边。至于直接建边。这样大大减少了边数。建完图后跑单源最短路。 代码： #include <bits/stdc++.h> #define lson rt<<1 #define rson rt<<1|1 #define IO...

题目： 小A给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度。欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次。 做法： 不难发现每条树边顶多用次，而且路径的起点和终点都是叶子。假如我们确定个叶子作为欧拉路的起终点。那么路径上的边算次，其他边算次。所以我们让这个路径最长，也就是选取树的某条直径端点作为欧拉路的两端，在直径上的边算次贡献，不在则次，就是答案。 代码： #include <bits/stdc++.h> #define ...

题目： 给个数，和个数。让你确定一个排列，使得序列。字典序最小。 做法： 其实是个贪心，每次从中剩下的数中选一个数，使最小，然后中删去。最后得到的序列就是答案了。所以重点是字典树的删除操作该怎么写。我的做法是，每个叶子记录一个，代表这个数的数量。每次删去一个数时，对应叶子结点的，如果变为，则删去该叶子，向上判断父亲结点是否变成了叶子，若是删去父亲，循环。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #...

题目： 给定一个非负整数序列，初始长度为。有个操作，有以下两种操作类型： ：添加操作，表示在序列末尾添加一个数，序列的长度。：询问操作，你需要找到一个位置，满足，使得： 最大，输出最大是多少。 做法： 我们直接看查询操作，它是要求序列的某个后缀的和，的最大值。我们设表示序列前个数的和。则其实是要求的最大值。而插入操作只是在末尾多加了一个数罢了，不会影响前面的，处理容易。由于和在每次询问时都确定的，我们设，则现在要解决的问题是：每个询问在区间中找一个，使的值最大。假如没有区间的限制，就是一个字典树。而加了区间限制意味着我们每次询问需要的是只包含一段序列的字典树，所以需要用到可持久化字典树。当我...

题目： 个点的无向完全图，每个点有点权，边权是点权的值。问最小生成树边权和。 做法： 最小生成树，经典老题了。做法是字典树上启发式合并。字典树上，按在左在右顺序，从左到右叶子表示的数的大小是有序的。所以我们先对点权从小到大排序，然后依次插入字典树上。这样字典树的子树下表示的数都来自原数组的一段连续区间，这便于我们处理。我们从高位到低位递归处理，先将子树和子树下的点各自分别联通，然后在这两个联通块上建一条边将其合并。这条边怎么选呢？我们可以枚举一棵子树下的所有数，在另一棵子树里查和其值最小的另一个数，这两个数建边的边权就是这个值。我们选边权最小的建边即可。而这个过程中，我们每次都枚举比较小的子...

题目： 给个数的序列，个操作。每次操作给一个，先使当前个数的序列一遍。然后求序列的输出。：未在序列中出现的最小非负整数。 做法： 根据的性质：序列。于是我们不用将累计在序列中，而是可以转化为累计在中。我们将个数插入字典树。每次操作相当于：给一个，在字典树中跑一个值最小且不在树上的数。其实本质还是用字典树实现高位贪心。字典树上每个结点维护该子树的，代表下面存的数的数量。若第位值为，先要判断其子树是否满了，若未满则代表了在该子树下，第位为。递归做下去就能一位一位得到了。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with...

题目： 给你个数。让你找出一个连续子序列其和最大。若方案不唯一，输出右端点最左的方案，若还不唯一，输出最短的方案。 做法： 对个数求的前缀和数组。问题转化成，在中选个数，其值最大。 做法见另一篇题解：https://blog.nowcoder.net/n/e27fd9137aed443f87b4c467a5d203d9 说明一下方案的输出思路：从左到右，统计选第个数和前个数中的某一个数值的最大值。若其值大于之前记录的方案，则该位置作为右端点更优。同时我们在上记录时保证选出来的左端点最靠右即可保证值最大的同时序列长度最短。具体就是在上插入同一个数时只记录后一个位置的。 代码： #incl...

题目： 在给定的N个整数中选出两个进行运算，得到的结果最大是多少？ 做法： 经典套路，字典树处理2个数的最值。其本质是一个贪心，高位若值为必定优于低位。我们把个整数依次插入字典树，每次插入前在字典树上跑一个贪心就能得到：前个数中选某个和第个数的最大值是多少。个数跑完取，最优解肯定在其中。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl us...