rk_no

题解

/ 注册

全部文章 / 题解（共71篇）

Propagating tree（欧拉序+线段树）

题目：给你一棵个结点的有根树，为根。结点有点权。个操作：：结点权值，的儿子们权值，的孙子们...以此类推；：询问当前的点权；做法：序：从根出发经过结点的顺序，每个结点只加一次，长度。欧拉序：从根出发绕回根沿途经过的结点的顺序，每进入结点加一次，长度。这题的更新操作中，我们发现其在欧拉序中是有...

2020-11-07

4 837

求和（dfs序+树状数组）

题目：给一棵以为根的有根树，点权。个操作，操作有两种类型：：表示将节点的权值加上；：表示求节点的子树上所有节点的和（包括结点本身）；做法：单点修改，求子树上的点权和。我们通过序可以将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。线段树或树状数组就行了。代...

2020-11-07

2 866

Colorful Tree（dfs序+lca）

题目：给一棵无根树。每个点有一个颜色。个操作。：将结点的颜色修改为；：问所有颜色为的结点的生成树大小。(若不存在颜色为的结点输出) 做法：这题好神奇。可以用序来维护相同颜色结点的生成树。考虑若颜色的只有个结点、，则其生成树大小就是两个结点在原树上的距离，记为。此时，如果加入第个结点，对生成树的...

2020-11-07

7 1409

Tree Requests（dsu on tree）

题目：给一棵树，每个点有一个英文字母。次询问，问子树内所有深度为的点里的字母能否重排成一个回文串。做法：处理子树上的询问，不带修改，询问可离线，我们可以考虑用。这是一种统计子树信息的方式，通过调整顺序，保留重儿子中的信息来优化复杂度。在这个题里，我们要做的就是对每棵子树，得到数组，代表这棵子...

2020-11-07

3 809

选点（dfs+LIS）

题目：有一棵个节点的二叉树，为根节点，每个节点有一个值。现在要选出尽量多的点。对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小；做法：题意转化一下。“右子树中选的点要比左子树中选的点小”反一下就是...

2020-11-07

2 750

Military Problem（dfs序）

题目：给你一棵有根树。个询问，输出从为根的子树往下得到的序列中第个数，超出则输出。做法：求出树的序。每个询问输出结点在中往后第个数。代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), ci...

2020-11-07

2 803

金字塔（区间DP或记忆化搜索）

题目：给一个类似序的序列。（经过一个结点记录一次颜色）。问有多少棵有根树满足（结点子树之间有序）。答案输出。做法：设为序列区间对应有根树的方案数，答案即为。转移思路：我们枚举区间对应的有根树里，第一棵子树的区间，设为，则其他子树对应区间。不难发现，合法的转移中，此时有最后加上只有一棵子树的情...

2020-11-05

1 865

Legacy（线段树建图，最短路）

题目：给个点。个操作。：和建权值的有向边；：和建权值的有向边；：和建权值的有向边；问从点到其他点的最短路。无法到达输出。做法：直接建图时间、空间复杂度都太大了。我们需要用线段树维护区间建图。开两棵线段树，自底向上建零边，自顶向下建零边。如下图：当我们处理这种情况时，只需用和线段树中的某些...

2020-11-04

5 1003

小A与欧拉路（树直径）

题目：小A给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度。欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次。做法：不难发现每条树边顶多用次，...

2020-11-03

2 846

Perfect Security（01字典树）

题目：给个数，和个数。让你确定一个排列，使得序列。字典序最小。做法：其实是个贪心，每次从中剩下的数中选一个数，使最小，然后中删去。最后得到的序列就是答案了。所以重点是字典树的删除操作该怎么写。我的做法是，每个叶子记录一个，代表这个数的数量。每次删去一个数时，对应叶子结点的，如果变为，则删去该...

2020-10-23

2 886