T1、 Giao 徽的烤鸭

又是树上问题，选择一个点的代价是 $ w_i $ ，选完所有点之后对于每个点 $ i $ ，找出最大的 $ d $ ，使得 $ d $ 满足 $ dis(j,i) \le d $ 的所有点 $ j $ 全部被选，那么你就可以获得 $ v_d $ 的收益，求最大净收益。

肯定是树上 $ DP $ ，我们考虑它有什么限制：就是对于一个点，如果他有 $ v_d $ 的贡献，那么就要求他方圆 $ d $ 内的点全部选上，那么就把他加入状态中。所以设 $ f_{i,j} $ 表示对于 $ i $ 点，他方圆 $ j $ 内的点必须全部选上，此时考虑完 $ i $ 及其子树的最大收益。

首先要求 $ f_{i,j} $ ，只能由 $ f_{k,p} , fa_k = i , p \ge j-1 $ 转移而来，因为一个点 $ i $ ，他要求 $ i $ 方圆 $ j $ 内都被选上，那么对于 $ k $ 方圆至少 $ j-1 $ 内必须都选上。

其次要注意到限制 $ j $ 是双向的，即对于 $ i $ 方圆 $ j $ 内的都选上，那么对于 $ fa_i $ 方圆至少 $ j-1 $ 内的都得选上，即 $ f_{i,j} \to f_{fa_i,k} , k \ge j-1 $ 。

综上所述，我们有转移方程式：

直接暴力转移即可，时间复杂度 $ O(n^2) $ 。

T2、 A Dance of Fire and Ice

首先注意到最后一个 $ 0 $ 操作前的操作都没有用，那么我们只考虑一个 $ 0 $ 操作和后面的一群 $ 1 $ 操作，于是就将题意转化成了一个数乘上一堆数的形式。

对于后面那一堆数，我们可以直接跑背包去做，然后枚举 $ 0 $ 操作的数再跑一遍类似背包的操作去计算答案，时间复杂度 $ O(np) $ 的。

考虑如何优化背包，乘法是难以优化的，而且注意到数据范围保证 $ p $ 是个质数，于是可以从正上面下手。有一个东西叫原根，它的性质就是：对于一个数 $ p $ ，他的一个原根 $ g $ ，满足 $ g_k , k \in [1,p-1] $ 两两互不相等，也就是说对于任意整数 $ x $ 满足 $ 1 \le x \le p-1 $ ，我们可以用 $ g_k $ 来表示他。

于是原根就将乘法转化成了加法，然后我们就可以用 std::bitset 优化背包，时间复杂度 $ O ( \frac{np}{w} ) $ ，好像过不去，但是我们过滤掉多余的操作，比如进行背包时，一个数 $ x $ 出现了多次，但对 $ x $ 做了几次背包后发现没有用了，那么 $ x $ 就永远没用了。这样复杂度就是 $ O(\frac{p^2}{w}) $ 的，刚好能过。

还有一个时间复杂度更优的是哈希加二分。仔细思考每次背包都是将原来区间右移一段后与原来区间或上，我们每次找出这两段区间第一个不一样的点，然后或起来。

首先如果我们每次找到的都是有用的点的话，那么只会找 $ O(p) $ 次，但是我们每次都可能会找到一些无用的点，但是我们考虑两个序列的和是一样的，那么每个上面是 $ 1 $ ，下面是 $ 0 $ 的不同会导致下面的和多 $ 1 $ ，那么这些 $ 1 $ 会被上 $ 0 $ 下 $ 1 $ 的给来回来，所以他们俩数量相等，于是就只有 $ O(p) $ 次，那么均摊就是 $ O(p \log ^2 p) $ 的 。（但是我没写）

T3、 挖掘机技术哪家强

图论结论太多了，完全不会啊。（