Home

如果不会建立虚树的话可以参考这个 题意 我们得到一棵树。这些节点中会定期选出几个关键点。对于所有的点他们受到距离他们最小的点且编号最小的点的控制，求最后每个关键点都会控制多少个点。 思路 我们不难想到一种树上 DP 的方式，首先先从子树向上传递，然后再由父节点向子树传递，就可以传递成功了。 但由于我们的询问轮数太多了，我们根本来不及一个一个传递。那么对于一些点我们建立一颗虚树。 我们记该点受 g[u] 点控制，其距离为 d[u]。 我们拷贝t=size[x] 并遍历点 x 的所有子树。 x 和 y 表示虚树上的两个节点，且 x 和 y 两个节点受到的控制点不一样。那么我们计算得出两个控制点之间的分界点 z(z 受到 x 控制)。 然后我们将这个分为三个部分 ...

题意 有 $n$ 个点，第 $i$ 个点连着 $a_i$ 点。其中每个点都有一个权值。对于每条边而言，其两端的点不可以同时加入总和。我们要求总和最大值。 思路 可以借鉴之前的blog 首先，这个图可以看出是一个个基环数组成。我们要求的就是所有基环数的总和最大值的和。 对于一个基环树，我们有入下图所示的样子。 从图中我们不难发现，我们有如下一个环，[1,12,7,14,4,11] ，如果我们断开其中一个路径，那么他的样子就成为树了，我们断开 [1,11] 这条路径。分别以 $1$ 为根和以 $11$ 为根做树形 dp。 先忽略环的影响，那么我们对于如下的树我们该怎么计算才能得到正确答案呢？ 我们设 f[i,0/1] f[i,0] 表示第 $i$ 个点不包含的最大...

https://www.luogu.com.cn/problem/P4381 题意 有 $n$ 个点，每个点 $i$ 都有一条出发到 $a_i$ 的边有权值 $w_i$ 。 求这些点形成的基环树他们的直径之和。 思路 对于这样的一个基环树 11 3 23 15 8 10 7 12 9 7 1 3 10 6 2 5 15 3 2 5 1 15 1 90 14 3 11 10 4 23 11 8 78 13 1 12 6 5 54 9 6 1 3 10 3 我们可以将其变形为这样 那么我们就得到了一个环和环上点的子树。 那么我们基环树的直径就变成了两个部分，要么是子树的最大直径，要么是环上最大长度。 对于子树最大直径不再赘述。 环上的直径如何计算呢。首先，我...

题意 我们有 $n$ 个点和 $n$ 个边，其中第 $i$ 条边连接至 $a_i$ 点。每条边需要指定一个方向。求问，有多少种方案使图中不出现环。 思路 我们可以发现，每个点的度至少为一，那么我们便可以得出以下的结论。 假如我们一共 $k$ 个连通图，那么我们这 $k$ 个连通图中边的数量一定等于点的数量。 如果边的数量等于点的数量的话，我们的图便是一个基环树，假若我们的图如下所示有多个基环树。 我们不难发现基环树可以拆分为两个部分 以紫色为边的环 以环的点为根的树 对于所有的树，无论我们怎么算都无法将其变为环图，因此我们只需要统计树中边的个数 $k$ 即可算出这部分的答案 $2^k$ 对于所有的环，我们只有两种方案（都朝向一个地方）让他们成为环，因此我...

题意 有一组两两各不相同的数字，每次我们可以进行如下的操作。 取两个数字 [x,y] 如果 gcd(x,y) 没有在这组数字中将其加入这组数据。 求问，最多可以加多少组数字。 思路 如果将每个数字进行唯一分解的话，我们可以发现我们添加的数字就是那些数字的相同部分。 如果我们将这个相同部分提取出来的话，那么剩下的部分进行 gcd 的话，他们的结果一定为 1. code

https://codeforces.com/contest/1624/problem/F 题意简述 这是一道交互式题目。 有一个数 $x$ 和一个数 $n$ 其中 $1\le x < n$ 你可以进行如下的询问: + c 将 $x$ 的值变为 $x + c$ 其中 $1\le c < n$ 然后返回一个值 $\lfloor\frac{x}{n}\rfloor$ 如果你在十次之内猜到的话则输出 $x$ 即可。 思路 由于我们只能得到 $\lfloor\frac{x}{n}\rfloor$ 那么我们不妨用二分的想法来考虑这个题目 对于我们上一个得到的 $k = \lfloor\frac{x}{n}\rfloor$ 我们可以分析出我们需要的数值一定...