0203测试

发表于 更新于 分类于

0203测试

考试

T1

参阅 该文章 20220309 部分。

无向图上的题不好做，考虑放到生成树上去做，我们这里为了方便，直接选取其 DFS 树。

边可以分为树边和非树边，容易发现选取非树边的子集之后，树边的选取方案就已经确定了。具体的，当且仅当一条树边被奇数条非树边覆盖的时候选取它，否则不选取。

考虑要求的东西 \(|S|^2\)，我们对于一个集合求子集权值和时，往往会考虑每个元素的贡献，这个也是一个道理，我们考虑一个有序对的贡献。

设非树边有 \(m\) 条分三种情况讨论：

  • 非树边和非树边：方案数为 \(m(m-1)2^{m-2}+m2^{m-1}=m(m+1)2^{m-2}\)。

  • 非树边和树边：首先树边必须至少被一条非树边覆盖，否则贡献为 \(0\)。在此基础上，限制是覆盖了树边的非树边集合必须选取奇数个元素，我们分两种情况讨论：

    • 非树边没有覆盖树边：方案数为 \(2^{m-2}\)，所有的子集中，有一半的集合没有选取非树边，在剩下的一半中，又有一半的集合不满足限制。
    • 非树边覆盖了树边：再分两种情况讨论：
      • 没有其它非树边覆盖了树边：方案数为 \(2^{m-1}\)，树边和非树边状态相同，只要非树边选了就一定合法。
      • 有其它非树边覆盖了树边：方案数为 \(2^{m-2}\)，所有的子集中，有一半的集合没有选取非树边，在剩下的一半中，又有一半的集合不满足限制。

  • 树边和树边：首先两条树边都至少被一条非树边覆盖。树边标号为 \(1,2\)，记只覆盖了 \(1,2\) 的非树边集合分别为 \(A,B\)，同时覆盖了 \(1,2\) 的集合为 \(C\)，其余集合为 \(D\)。因为每条树边都被覆盖，所以 \(|A|+|C|>0\) 并且 \(|B|+|C|>0\)。剩下的情况分三种讨论：

    • \(|A|+|B|=0\)，此时 \(|C|>0\)，\(1,2\) 边的选取状态一定相同，对于 \(C\) 集合，选取的元素个数必须为奇数，因此有一半的子集不满足条件，答案 \(2^{m-1}\)
    • \(|A|=0,|B|>0\)：有一半的子集，不满足覆盖 \(1\) 的非树边个数为奇数。在剩下的一半中，又有一半的子集不满足覆盖 \(2\) 的边数为奇数。
    • \(|A||B|>0\)：有一半的子集，不满足覆盖 \(1\) 的非树边个数为奇数。在剩下的一半中，又有一半的子集不满足覆盖 \(2\) 的边数为奇数。

    对于后两种情况的理解，我们可以视为是解一个 01 异或方程组，求自由元的个数，后两者线性基的大小都为 \(2\)，而 \(|A|+|B|=0\) 的线性基大小为 \(1\)。

    用更像人话的方式表达，对于 \(|A||B|>0\) 的情况，从 \(A,B\) 中各拿出一个元素来，其它元素任选，方案数 \(2^{m-2}\)，选定了这些元素之后，剩下的两个元素的选择方案就固定了。注意具体拿 \(A,B\) 中的哪个元素并不影响结果。因为这样生成的方案和合法方案是一一对应的。

    \(|A|=0,|B|>0\) 的情况同理，只不过是从 \(B,C\) 中各自拿出一个元素，先决策 \(C\) 中的元素，再决策 \(B\) 中的元素。

上面讨论中，第一部分是容易的，第二部分我们只需要求出每条树边由多少条非树边覆盖也可以轻松统计答案，可以用树上差分来完成。

第三部分相对困难，我们发现 \(|A|+|B|=0\) 当且仅当覆盖两条树边的非树边集合相同，于是就是对于若干个集合，计算有多少个两两相同。

集合的判重可以采用异或哈希的方式，给每一条非树边一个随机的 \([0,2^{64})\) 的权值，并将其覆盖的路径上的树边都异或上这个权值，如果两条树边的权值相同，那么我们可以认为两条树边对应的非树边集合相同，树上路径异或还是可以差分实现。

一次判断的错误率为 \(2^{-64}\)，由于我们是统计的集合相同的对数，因此等价于进行了 \(n^2\) 次判断，但错误率还是在可以接受的范围——约 \(10^{-8}\)。

T2

参阅 该文章 20220329 部分。

参阅 简单数论函数和应用。

\(p\) 代表一个质数。

不难证明 \(f(n)=\gcd(n,n')\) 是积性函数，令 \(f(1)=1\)，由于 \(f(p)=1\)，可以考虑 PN 筛。

构造 \(g(n)=\boldsymbol{1},h=f/g\)。

考虑 \(h\) 在 \(p\) 处的取值，有 \(f(p)=h(1)g(p)+h(p)g(1)\)，代换得 \(h(p)=1\)，由于 \(h\) 为积性函数，所以仅在 PN 处有取值。

推一下公式： \[ \begin{align} \sum\limits_{i=1}^nf(i)&=\sum_{i=1}^n\sum_{d|i}h(d)g(\frac{i}{d})\\ &=\sum_{d=1}^nh(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}g(i)\\ &=\sum_{d=1}^nh(d)\lfloor\frac{n}{d}\rfloor\\ &=\sum_{d\in \operatorname{PN}}^nh(d)\lfloor\frac{n}{d}\rfloor\\ \end{align} \] 如何求 \(h\) ？

简单做一下代换： \[ h=f/\operatorname{\boldsymbol{1}}=f * \mu \] 考虑 \(h(p^c)\) 的取值，有 \(h(p^c)=\sum\limits_{i=0}^cf(p^i)\mu(p^{c-i})=f(p^c)-f(p^{c-1})\)，构造完成。

T3

参阅 该文章 LCA 性质部分。

非常奇妙的贪心题。

用人话说一遍题意：有一棵边带权的树，\(q\) 次强制在线询问，每次给定 \(u,k\)。你需要选择 \(k\) 条路径，使得它们至少有一条过 \(u\)，并且路径经过边集的并的权值最大，一个边集的权值等于所有边的权值和。

选路径是很麻烦的事情，但是可以转化为选点，感觉上选叶子是比较好的。

\(\text{Lemma 1.}\)

对于一个定点 \(u\)，最优方案的路径的端点都在叶子上。

\(\text{Proof 1.}\)

如果某条路径的某个端点不在叶子上，我们让它往使得这条路径变长的方向移动，就可以将所有端点移动到叶子上。

\(\text{Lemma 2.}\)

以任何一个点为根，不考虑经过 \(u\) 的限制。对于一个叶子的可重集 \(S\)，存在一种选择 \(\lceil\frac{|S|}{2}\rceil\) 条路径的方案，经过 \(S\) 虚树上的所有边，并且是所有端点可重集为 \(S\) 的路径选择方案中权值最大的方案。

\(\text{Proof 2.}\)

证明分两步——"最大"和"值"，这里会用到一些开头参考资料中的定理。

最大：不在虚树上的边无法经过。

值：设点集为 \(S\)，\(k=1\) 时结论成立，令 \(u=\operatorname{lca}(S)\)。归纳的，设结论在 \(k<n\) 时成立，对于 \(k=n\)，分两种情况讨论：

  • 存在一个点有超过 \(k\) 个叶子：记这个子树叶子集合为 \(S'\)，令 \(u'=\operatorname{lca}(S')\)，选择 \(S'\) 若干个 dfs 序不是最大也不是最小的点，记为 \(T\)，使得 \(|S'-T|\) 是 \(2\) 的倍数，且 \(T\) 的大小和 \(u\) 次大的的子树相同或者仅多 \(1\)。读者可以尝试证明这样的 \(T\) 一定存在，此处略去证明。

    对于 \(S-S'+T\) 中的点来说，它们存在一种覆它们存在一种覆盖对应虚树的方案，所以 \(u'\) 到 \(u\) 的路径一定已经被覆盖了。对于 \(S'-T\) 中的点来说，也存在一种覆盖虚树的方案。由 lca 性质，\(\operatorname{lca}(S'-T)=u'\)，所以两个点集并起来后的虚树也都被覆盖了。

  • 不存在一个子树有超过 \(k\) 个叶子：这种情况让不在同一子树的叶子配对最优，因为每个叶子都到了 \(u\) 点，一定覆盖了虚树。

由 Lemma 2，如果确定了最优方案端点的可重集 \(S\)，那么就可以确定最优方案的权值，所以问题变成了选叶子。

即选一个大小为 \(2k\) 的叶子集合，集合权值为其虚树上的边的权值和，要求 \(u\) 在其虚树上，最大化集合权值。

\(\text{Theorem 3.}\)

以 \(u\) 为根，如果最后选取的最优虚树经过 \(u\)，那么每次贪心的选取能使得答案增加量最多的叶子，能取到最优值。

\(\text{Proof 3.}\)

考虑最优的叶子选择顺序 \(a_1,a_2,a_3\cdots a_n\)。

假设最优选取方案前 \(k\) 个和贪心的顺序相同，第 \(k+1\) 个不同，设应该被贪心选取的点为 \(u\)，往上跳 \(u\) 的父亲直到和 \(\{a_i,i>k\}\) 构成的虚树相交，分情况讨论：

  • 如果找不到交点，替换后面的任意一个选择都会更优。考虑选完所有点后移除 \(a_x,x>k\)，带来的的权值减少量。它不会多于在选完 \(a_k\) 后选择 \(a_x\) 的权值增加量，所以也不多于选完 \(a_k\) 后选择 \(u\) 的权值增量，因此更优，注意到这种情况下选完所有点后选择 \(u\) 的权值增量等于选完 \(a_k\) 后选择 \(u\) 的权值增量。
  • 如果能找到交点，在这个交点的子树内选一个点移除，同样选 \(u\) 的增量大于移除那个点的减少量。

在 Theorem 3. 中我们假定了最后一定经过 \(u\)，以便于计算单选一个叶子时的答案，如果以上贪心策略不经过 \(u\)，那么只需要将最后一次的选择替换为 \(u\) 不同儿子的最深叶子即可。

因此我们对于一个点的情况得到了一种贪心做法，这个贪心做法直接实现需要维护每次选择后每个叶子的权值，但是并不好维护这个东西。正难则反，考虑选取每个叶子时它的权值，它一定是一条从自身到根的路径的下半部分。容易发现上端点是第一个最深叶子不是它的祖先。记点 \(u\) 子树下最深的叶子为 \(down[u]\)，那么一个叶子 \(x\) 的权值是它到第一个 \(down[u]\ne x\) 的 \(u\) 路径的长度，\(down[1]=x\) 是例外。

因此，我们可以提前计算出选每个叶子时贡献，这个贡献是最优方案下的贡献，如果一个选取方案不是最优方案，那么这个贡献是不对的，我们利用了方案一定最优这个性质去简化了求权值的过程。

计算答案即取前 \(2k\) 大，如果前 \(2k\) 大在根的同一子树，那么取消最后一次的选择换成一个不同子树的。

先考虑不强制在线的做法。

考虑换根的过程，哪些叶子的权值会变化，不妨设从 \(u\) 到 \(v\)，边权为 \(val\)，首先 \(down[v]\) 的权值会减少 \(val\)，其次时到 \(u\) 最远的叶子的权值会增加 \(val\)，考虑到 \(u\) 最远的叶子时需要排除 \(v\) 方向的。

然后变化量是常数级别的，线段树即可。

对于强制在线的情况，如果我们能快速得到每个点的线段树事情就好办了，不强制在线的时候我们确实可以求出在每个点处的线段树——可持久化。

简单总结一下比较妙的点：

  • 利用方案是最优方案的性质，我们将选路径问题转化为了选点问题（Lemma 2）。

  • 贪心过程中，我们需要维护每个点的贡献，并选取贡献最大的点。选取贡献最大的点后其它点的贡献会变化，变化量不容易维护，于是考虑每个点被选取时的贡献。将方案最优作为一个已知条件，借此条件我们能够计算出每个点被选取时的贡献。

  • 将此题强制在线后，我们不太好利用根移动一个位置后贡献变化量为常数的性质，因为总的移动量是 \(O(n^2)\)，但是树的形态不会改变，因此我们在每个位置查询的线段树都不会改变，我们能通过 dfs 求出每个位置查询的线段树的形态，将它可持久化即可在任意时刻查询。