世界树
如果不会建立虚树的话可以参考这个
题意
我们得到一棵树。这些节点中会定期选出几个关键点。对于所有的点他们受到距离他们最小的点且编号最小的点的控制,求最后每个关键点都会控制多少个点。
思路
我们不难想到一种树上 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$ 个点不包含的最大...
Island
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
我们可以将其变形为这样
那么我们就得到了一个环和环上点的子树。
那么我们基环树的直径就变成了两个部分,要么是子树的最大直径,要么是环上最大长度。
对于子树最大直径不再赘述。
环上的直径如何计算呢。首先,我...
Directed Roads
题意
我们有 $n$ 个点和 $n$ 个边,其中第 $i$ 条边连接至 $a_i$ 点。每条边需要指定一个方向。求问,有多少种方案使图中不出现环。
思路
我们可以发现,每个点的度至少为一,那么我们便可以得出以下的结论。
假如我们一共 $k$ 个连通图,那么我们这 $k$ 个连通图中边的数量一定等于点的数量。
如果边的数量等于点的数量的话,我们的图便是一个基环树,假若我们的图如下所示有多个基环树。
我们不难发现基环树可以拆分为两个部分
以紫色为边的环
以环的点为根的树
对于所有的树,无论我们怎么算都无法将其变为环图,因此我们只需要统计树中边的个数 $k$ 即可算出这部分的答案 $2^k$
对于所有的环,我们只有两种方案(都朝向一个地方)让他们成为环,因此我...
Interacdive Problem
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$ 我们可以分析出我们需要的数值一定...
54 post articles, 7 pages.