UOJ Round #17
A. 滑稽树上滑稽果
5
$n \le 5$
暴力枚举每个点的父亲。
时间复杂度 $\mathcal O(n^n)$。
15
$n \le 12$
保证存在合法的最优解是一条链
暴力枚举所有排列。
时间复杂度 $\mathcal O(n!)$。
25
$n \le 100$
保证存在合法的最优解是一条链。并且从根开始的每个滑稽值构成了一个序列，保证解的这个序列的字典序，在所有链对应的序列中最小
每次枚举和当前的滑稽值 and 起来最小的值加到后面。
时间复杂度 $\mathcal O(n^2)$。
40
$n \le 10^5$
保证存在合法的最优解是一条链。并且从根开始的每个滑稽值构成了一个序列，保证解的这个序列的字典序，在所有链对应的序列中最小
把相同的位提出来，这些位要么一定是每次没贡献，要么一定是每次有贡献。
剩下的位，每次一定会减去一位，从而最多只会用 $\mathcal O(log a)$ 次就减到 $0$ 了，每次暴力找最小的。
时间复杂度 $\mathcal O(n \log a)$。
70
$n \le 100$
部分分的贪心过程可能是错的。
把相同的位提出来，剩下的位我们希望尽快把他们变成 $0$。
考虑 DP，记 $f[S]$ 表示 $S$ 集合内的位为 $1$ 的时变成 $0$ 的最小代价。
每次枚举 $a[i]$，$f[S] = \min(f[S], f[S \& a[i]] + (S \& a[i]))$。
时间复杂度 $\mathcal O(n a)$。
100
$n \le 10^5$
可以每次不枚举一个 $a[i]$，而是枚举一个子集 $T$，强制把这个子集 $T$变成 $0$。
现在的问题是判断有没有一个数和 $T$ and 起来是 $0$。
| 每次 $cnt[i] | = cnt[i | (2^j)]$，从每个比 $i$ 多一个 $0$ 的位置转移就好了。 |
事实上，DP 时可以用贪心得到的解来进行剪枝。
时间复杂度 $\mathcal O(a^{log_2 3})$。
B. 滑稽树下你和我
5
$\mathrm{stx}$ 和 $\mathrm{sty}$ 均为叶子
直接输出两点距离。
20
保证存在最优方案，在任意时刻至少有一端点位于树的某结点上
考虑二分答案，记 $f[i][j]$ 表示是否存在某种方案使得最终一个点在点 $i$，一个点在点 $j$。
时间复杂度 $\mathcal O(n^2 \log n)$。
100
$n \le 1000$
对于两个状态，两个点所在的边相同，并且两个状态的两点间距离 $\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 转移即可。
单次转移复杂度为 $\mathcal O(deg_i)$，总时间复杂度 $\mathcal O(n^2 \log n)$。
C. 滑稽树前做游戏
10
$m = n - 1$，且 $a_i = 1$。
菊花图情况下答案为 $\frac{1}{2} + \frac{n - 1}{n}$。
30
$n \le 4$
手算打表。