260227 模拟赛

考虑一个长为 \(n\) 的序列，你需要选一些二元组或多元组，元组也有自己的限制，然后让某些位置至少被一个二元组覆盖。每个位置的限制形如一个存在性问题，这样的东西没法直接做，只能直接容斥成一些位置不存在其余位置不管。

T1

显然只需对所有叶子满足条件即可。那么条件等价于所有叶子一步能走到的点集两两有交，因为点集都是连通块，所以等价于所有点集存在公共部分。

直接对公共部分进行子集反演是没有前途的，注意到它是一个连通块，所以考虑进行点边容斥，让每个点产生 \(+1\) 的贡献，每条边产生 \(-1\) 的贡献，这样每组合法方案就会恰好有 \(1\) 的贡献。此时问题转化为钦定每个点属于公共部分的方案数，以及钦定每条边属于公共部分的方案数。

对于一个点 \(u\)，我们将它旋转到根，要求所有叶子（排除 \(u\)）都存在一条经过 \(u\) 的路径。注意到连接两个叶子的路径非常不好处理，只能容斥成钦定一些叶子只向子树内有路径。考虑 dp，设 \(f_i\) 表示考虑了一个前缀的子树，钦定了 \(i\) 个叶子不满足。那么转移形如加入一棵子树：

\[ f_i\times \binom{leaf_v}{j}2^{\binom{sz[v]}{2}}2^{(sz[v]-j)(cur-i)}\to f'_{i+j} \]

其中 \(cur\) 表示已经考虑的子树的 \(sz\) 之和。这样直接做显然是 \(O(n^3)\) 的。发现如果不处理外子树那么就可以应用树上背包的分析，做到 \(O(n^2)\)。由于外子树只有一个，因此可以钦定外子树的所有叶子都满足条件。最后加入外子树，形如

\[ f_i\times(2^{sz[u]-i}-1)^{leaf_{out}}(2^{sz[u]-i})^{n-sz[u]-leaf[out]}\to ans \]

然后边的贡献其实就是只有一棵子树的特殊情况，直接枚举 \(u\) 子树内有多少个叶子不满足限制即可。需要快速幂，所以复杂度其实是 \(O(n^2\log n)\)。瓶颈处其实带个 \(\frac{1}{2}\) 的小常数所以其实只有 \(4\times 10^6\) 次快速幂。

T2

赛时想到了 \(O(n^5+Qn)\) 做法，没想到能过。具体就是超过一天显然可以通过两边 Dijkstra 预处理答案，少于一天则离线所有询问，对于一个起点按照起始时间从大往小处理，每次加边就暴力重构。海亮 oj 能过，我实现太劣了所以洛谷过不了。

考虑优化，注意到对于一条路径 \((u\to v,d_0)\)，其中必有一条限制最紧的边，即 \(c'(u,v)-d_u\) 最小的边。我们枚举这条边，然后只走 \(c'(u,v)-d_u\) 更大的边，正反跑两边 Dijkstra，然后更新所有点对的答案。最后需要排序，查询需要二分，所以复杂度是 \(O(n^4\log n+Q(n+\log n))\)。