滑稽树上滑稽果

By jiry_2，数据、题解By WuHongxun

写题解之前，我们先来回顾一下上次比赛的A题题解：

这道题可能并没有那么有趣..本来有一道很棒的 A，但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。

懂我意思吧？

如果看到题面里大大的滑稽还没有察觉事情不太对...请允悲...

子任务一

既然 $n$ 那么小，我们直接枚举每个点的父亲！

时间复杂度 $O(n^n)$。

子任务二

保证是一条链了，我们就只要枚举排列了！

冷静一下马上就会意识到，答案一定是一条链。这个部分分肯定是出题人用来提示大家冷静一下的！

时间复杂度 $O(n!)$。

子任务三

保证滑稽值的字典序最小？那就等于是每次枚举一个和当前的滑稽值and起来最小的值，然后把他加到后面。

时间复杂度 $O(n^2)$。

子任务四

把相同的位拿出来，这些位要么一定是每次没贡献，要么一定是每次有贡献。

那么剩下的位，每次一定会减去一位，从而最多只会用$O(loga)$次就减到0了，每次暴力找最小的就好了。

时间复杂度 $O(nloga)$。

子任务五

出题人给了一个部分分是这个贪心的过程，我们睿(ruo)智(zhi)的分析一下，这个做法一定是错的！

事实上的确是希望考验大家独立思考、小心求证的能力。

我们一样先把每个数都一样的那些位拿出来，剩下的位我们等于是希望尽快把他们变成$0$。

这可以用一个dp来实现，$f[S]$表示$S$集合内的位为1的时候，想要变成$0$还需要多少代价。

dp转移就是每次枚举一个$a[i]$，$f[S]=min(f[S],f[S\mathrm{\&}a[i]]+(S\mathrm{\&}a[i]))$。

时间复杂度 $O(na)$。

子任务六

我们可以每次不枚举一个$a[i]$，而是枚举一个子集$T$，强制把这个子集$T$变成$0$。

现在的问题就是，判断有没有一个数他和$T$，and起来是0。

这非常好做，只需要每次$cnt[i]|=cnt[i|(2^j)]$，从每个比$i$多一个$0$的位置转移就好了。

事实上dp的时候，我们可以用贪心得到的解来进行剪枝，所以是不卡常数的。

时间复杂度 $O(a^{lo{g}_{2}3})=O(a^{1.58})$

滑稽树下你和我

By picks，数据、题解By Scape

算法一

直接输出两起始点距离即可。

期望得分$5$分。

算法二

考虑"保证存在最优方案，在任意时刻至少有一端点位于树的某结点上"这个性质。

我们先考虑二分答案，显然可以设计一个dp即为$f[i][j]$表示是否存在某种方案使得最终一个点在点$i$,一个点在点$j$。直接按照定义转移即可，时间复杂度$O(n^{2}logn)$

期望得分$15$分。结合算法一可获得$20$分。

算法三

同样我们先考虑二分答案，看答案是否能$\le v$。

我们考虑一条这样的性质。对于两个状态，两个点所在的边都相同，并且两个状态的两点间距离是$\le v$的，那么这两个状态是两两可达的。因为我们考虑是把其中某一条直线摆平，那么另外一条直线肯定是单调的。

那么我们就可以依此设计状态，令$f[i][j]$表示是否存在某种方案使得一个点在点$i$上，一个点在边$j$上距离点$i$最近的那个点上。那么$f[i][j]$为$1$当且仅当点$i$到边$j$的最短距离$\le v$且存在某个$f[k][x]$为$1$,其中$k$是$j$的某个端点,$x$是某个以$i$为端点的边，或存在某个$f[t][j]$为$1$，其中$t$与$i$有边相连。直接BFS转移就可以了。

因为我写完这个东西已经是早上凌晨三点了，所以我当时就认为这个算法是$O(n^{3}logn)$的，这就是$n\le 200$这个Subtask的由来。（笑

我们仔细分析一下，$f[i][j]$的转移复杂度显然是$O(i\mathrm{的}\mathrm{度}\mathrm{数})$的。那么加起来的转移复杂度总和显然是$O(n^2)$的，所以整个算法复杂度是$O(n^{2}logn)$的，你也可以选择不二分答案而是类似最短路那样去做，但还是要sort或者用堆维护，复杂度不变。

期望得分$100$分。

滑稽树前做游戏

By jiry_2

算法一

如果你做过 这个题，你就肯定知道菊花树的情况下答案就是 $\frac{1}{2}+\frac{n-1}{n}$。用快速幂求个逆元就可以了。

期望得分 $10$ 分。

算法二

$n=4$ 的本质不同的图只有 $11$ 种，如果你有高超的手算水平，相信你可以算出所有 $n\le 4$ 的图的答案，然后打表。

结合算法一期望得分 $30$ 分。

算法三

这题据我所知有很多种复杂度较高的 DP 算法可以通过 $n\le 10$ 的数据，但是都没有标算简洁优美，这儿就不进行介绍了。

和大部分期望题一样，令 $g(t)=Pr[f(x)\le t]$，那么答案显然就是 $2-{\int }_0^{2}g(t)\text{d}t$，因此我们只需要求出函数 $g(t)$，并做一次积分即可。

我们把题目的输入看做一张 $n$ 个点 $m$ 条边的无向图 $G$，那么 $g(t)$ 是一个关于 $G$ 的函数。

定义函数 $h(G,y,t)$，表示在无向图 $G$ 中，所有顶点权值的最大值小于等于 $y$，答案小于等于 $t$ 的概率，并且我们限制这个函数的定义域为 $\frac{t}{2}\le y\le min(1,t)$。现在我们来考虑如何计算得到 $h(G,y,t)$：

1. 如果所有点的权值都小于等于 $\frac{t}{2}$，那么必定满足顶点权值最大值小于等于 $y$，因此此时的概率为 $(\frac{t}{2}{)}^n$（令 $G$ 的顶点个数为 $n$）。

2. 如果至少有一个点的权值大于 $\frac{t}{2}$，我们枚举权值最大的点 $i$，设它的权值为 $w$。考虑所有与 $i$ 相邻的点 $j$，所有 $j$ 的出边中，权值最大的就是边 $(i,j)$ 了，因此 $j$ 的权值应当小于等于 $t-w$（又 $w>\frac{t}{2}$，因此不会和其他限制导出矛盾）。我们删去第 $i$ 个点和所有相邻点，得到了图 $G_i$，那么 $G_i$ 中的点应当满足点权小于等于 $w$ 且答案不超过 $t$，即概率为 $h(G_i,w,t)$。

因此，我们得到了关于函数 $h(G,y,t)$ 的递推式：

$$h(G,y,t)=(\frac{t}{2}{)}^n+\sum _{i=1}^n{\int }_{\frac{t}{2}}^{y}h(G_i,w,t)\text{d}w$$

显然有 $h(G,y,t)$ 是关于 $y$ 和 $t$ 的 $n$ 次其次多项式，于是我们对 $G$ 进行状压，可以在 $O(2^n{n}^3)$ 得到 $h(G_0,y,t)$，其中 $G_0$ 为输入的图。那么这时 $g(t)=h(G_0,min(1,t),t)$，直接积分就可得到答案。

时间复杂度 $O(2^n\times n^3)$，结合算法一可以得到 $70$ 分。

算法四

怎么在算法三种作优化呢，我们发现算法三的复杂度的一个上界是子图个数，但是很多时候又不慢，比如在图是一个团的时候，$G_i$ 均为空，会计算的子图只有 $O(n)$ 个。

那是不是算法三可以直接跑过 $25$ 呢，遗憾的是并不是。不难发现在输入是一棵菊花的时候，算法三就会跑慢 $2^n\times n^3$。但是其中大部分的子图都是不连通的。

不难发现对于一张不连通的图 $G$，它的联通块分别为 $G_1,...,G_m$，那么 $h(G,y,t)=\prod _{i=1}^{m}h(G_i,y,t)$，因此对于不连通的图，我们可以直接拆分成更小的子问题，而不是和算法三一样递归的搜索。

时间复杂度未知，可以得到满分。

虽然我不会分析复杂度，但是实际上对于所有我能构造的 $n=30$ 的图，这个算法都可以在 $0.2s$ 内出解。于是冷静了一下就把 $n$ 开到 $25$ 出了出来。

这一题目前一共有 $157$ 个测试数据，std 一共只需要跑 $160ms$，所以应该是不存在卡常数的可能性的。