A 未来
注意树是按照 prufer 序随机生成的，因此树高期望为 $\sqrt n$ ，我们考虑对于每个点，计算它的所有祖先对它的贡献。
比如设当前考虑的点为 $u$ ，其祖先为 $v_1$ ，考虑设祖先到这个点的路径是 $v_1,v_2\dots v_k,u$ ，我们知道 $u$ 的贡献只和这个路径的点在排列中的相对顺序有关。那么怎么计算 $v_1$ 对 $u$ 的贡献？
我们不妨暂时将这条链重新编号，看成 $1,2,\dots k$ ，我们要统计所有排列下 $1$ 对最后的 $u$ 点的贡献。发现这个贡献其实就是所有排列的以 $1$ 开头的上升子序列个数和！考虑某种排列的某条上升子序列 $p_1,p_2,\dots p_t$，我们考虑这样一种贡献 $p_1 \to p_2 \to\dots \to p_t \to u$ ，这样就会有一种方案对 $u$ 造成了贡献。每种上升子序列对应唯一一种造成贡献的方法。
这个个数很好求，考虑枚举有多少个在 $1$ 后面的数，然后相当于我们已经钦定了这 $j + 1$ 个数字的位置，剩下的数任意排列的方案。
这个可以直接暴力预处理。因为树高度期望下是 $O(\sqrt n)$ 的。
注意最终需要加上自己本身最后的贡献以及最后自己对自己的贡献（未被计算），也就是 $2\times n!\times \sum v_i$
最终复杂度 $O(n\sqrt n)$ 。
1 |
|
B 幸运
我们先考虑无修改的情况。
假设到达每个点的概率是 $p_i$ ，每个点到根的距离是 $l_i$ 。那么走到 $k$ 的期望次数就是 $\frac 1 {p_k}$ 。也就是说我们有 $\frac 1 {p_k} - 1$ 次是不经过 $k$ 走到某个叶子。那么期望步数是 $\frac{\sum_{i\in leaf,i\notin k} ( l_ip_i )}{\sum_{i\in leaf,i\notin k } p_i}$ 。
为了方便，不妨设 $p = p_k$ ，于是这个步数就是
所以所需要的时间是
于是可以过 50 pts。
我们考虑可以离线询问，然后整个树的形态就有了。首先我会计算 $l_i$ ，维护深度即可。
然后我们要维护的是 $p$ 以及 $\sum_{u \in leaf,i\notin k} l_ip_i$。
维护子树信息，放到 dfs 序上就变成了区间操作。
我们考虑打一种 “不是叶子” 标记，打了这个标记后子树内的 $p_i,p_il_i$ 都不参与计算。
维护 $p$ ？我们可以直接维护到达每个叶子的概率 $p_i$ 。考虑删除一个子树的操作。假设删除 $u$ 为根的子树， $u$ 的父亲为 $f$ ，$f$ 原本儿子个数是 $s$ ，那么相当于其他子树内的点都乘上 $\frac s {s-1}$。撤销删除同理。于是 $p$ 的计算就是子树求和。
维护 $\sum l_ip_i$ ? 不难发现这和刚刚那个是同一个道理，仍然是区间乘上 $\frac s {s-1}$ 。
添加和删除的时候，需要更新父亲节点以及这个点的 “是叶子“ 标记。
1 |
|
C 重逢
我们考虑一种分组方案，每种方案有 $b_i$ 个。我们认为一种放石的方案是特殊的，当且仅当 $b_i \equiv -1 \pmod {2\times p_i}$ 。
如果第二个人复读第一个人的决策，那么：
对于不特殊的石子，第二个人可以模仿第一个人的决策，第一个人只能拿到 $(\lfloor \frac {b_i}{2p_i}\rfloor) val_i$ 的分数。
对于特殊的石子，第二个人可以模仿第一个人的决策，第一个人只能拿到 $(\lfloor \frac {b_i}{2p_i}\rfloor + 1) val_i$ 的分数。
于是现在的最优决策就是，拿场上权值最大的特殊石子，然后交替拿。对于第二堆也类似。
我们设第一堆的石头从大到小是 $v_1,v_2,\dots$ ，第二堆是 $w_1,w_2\dots$ ，那么第一个人能够得到的最优答案就是
于是我们可以设 $dp[i][j][0/1][0/1]$ 表示考虑到了第 $i$ 个石头，当前第一堆石头已经有 $j$ 个，当前第一堆石头在放第奇数还是偶数个特殊石子，当前第二个在放奇数还是偶数。
最后答案就是 $dp[n][\sum \frac{a_i}{2}][0/1][0/1]$ 。
复杂度是 $O((\sum a_i)^2)$。可以通过 subtask 4。
考虑如何优化这个过程？发现 subtask 5 给了个提示，一个关于 $a_i$ 的奇妙的石子很小。
发现在一堆石子中放入 $a_i,a_i+2p_i$ 得到的答案是一样的。所以我们不妨直接给 $a_i$ 模 $p_i$ 来做，这样 dp 的第二维就很小了。
这么来看，这一部分的 dp 复杂度是很优秀的，仅仅是 $O((\sum p_i)^2)$ 。
但是我们还得考虑剩下的可以自由分配的石子，这种石子是一组一组的，每组 大小是 $2p_i$ ，我们设 $r_i$ 是放在某一堆石子的数量模 $2p_i$ 的余数，于是考虑两种情况：
- $r_i \leq a_i \pmod{2p_i}$ 这种情况下，可以自由分配 $\lfloor \frac{a_i}{2p_i} \rfloor$ 组石头。
- $r_i > a_i \pmod{2p_i}$ 这种情况下，可以自由分配 $\lfloor \frac{a_i}{2p_i} \rfloor - 1$ 组石头。
如果这么做，分配的组数都不一样很毒瘤。于是考虑当 $r_i \le a_i$ 的时候，我们尝试分配一下 $r_i,r_i+2p_i$ ，于是自由分配的组数必然是 $\lfloor \frac{a_i}{2p_i} \rfloor - 1$ 。
这里对于自由分配的组，我们需要做个背包，看能不能凑出 $0,1,2,\dots$ 。
这样复杂度是 $O((\sum p_i)^2+(\sum a_i)(\sum \frac{a_i}{2p_i}))$ 。可以通过 subtask 5 。
这个前半段的复杂度已经很优秀了，考虑优化后半段。这个背包可以进行二进制分组，比如将 $1000$ 分成 $1,2,4,8,16,32,64,128,256,489$ 这些物品。于是可以把 $\frac{a_i}{2p_i}$ 拆成这种东西来背包，用 bitset 来优化，复杂度是 $O(\frac{n(\sum a_i)(\log \sum a_i)}{w})$ 。可以通过 subtask 6。
最后，注意到 $\sum p_i \le 2000$ 意味着 $p_i$ 的种类数量其实只有 $\sqrt{\sum p_i}$ 。于是可以合并相同的 $p_i$ ，即可通过本题。
1 |
|