P10546 [THUPC 2024 决赛] 采矿 题解

:::info[Description] Link. :::

:::infoSolution 考虑给每个开关 $i$ 随机生成一个 $50$ 位的二进制数 $mask_i$ 满足每一列恰好有 $25$ 个 $1$ 且任意两个 $mask$ 都不相同也不互为反码。这样第 $i$ 次询问的时候让第 $j$ 个开关的状态就是 $mask_j$ 在二进制表示下的第 $i$ 为字，这样每条边在 $50$ 次询问中恰好两个方向分别出现了 $25$ 次。

记 $f_{i,j}$ 表示第 $i$ 次询问中结点 $j$ 的答案。然后考虑从叶子开始往根转移答案。记 $w_{i,j}$ 表示第 $i$ 次询问中结点 $j$ 的答案。则一开始每个点都只代表自己，所以有 $w_{i,j}=1$。对当前树的叶子结点 $x$ 设其的唯一一个邻居结点为 $y$，则考虑分类讨论：

• 若边的方向是 $x\to y$ 则外面任何一个结点都无法到达 $x$，所以显然有 $f_{i,x}=w_{i,x}$。
• 若边的方向是 $y\to x$ 则任何一个能到 $y$ 的结点都能到 $x$，转移就是 $f_{i,x}=f_{i,y}+w_{i,x}$。

然后考虑怎么找叶子。显然一个结点 $x$ 是叶子当且仅当满足条件 $f_{i,x}=w_{i,x}$ 的 $i$ 恰好有 $25$ 个。证明是容易的，对于叶子而言，这个等式恰好在唯一的边方向为 $x\to y$ 上成立。反过来，如果 $x$ 结点不是叶子，那么至少还有两条相邻边。要让 $f_{i,x}=w_{i,x}$ 成立，则所有的剩余相邻便都必须同时从 $x$ 指向外部。任意取出其中的两条边，因为她们对应的 $mask$ 不相同而且还不互为反码，因此两条边同时朝外的次数必然严格小于 $25$。因此必然不满足条件。

找到叶子 $x$ 后考虑构造一个新的 $50$ 位二进制数 $s$，使得其第 $i$ 位为 $1$ 当且仅当 $f_{i,x}=w_{i,x}$。由上面的分析可得 $s_i=1$ 当且仅当第 $i$ 次询问的边的方向为 $x\to y$。因此 $s$ 一定等于控制这条边的某个 $mask_j$ 或者其反码。若 $s=mask_j$ 则说明开关为 $1$ 时边的方向是 $x\to y$，也就是初始方向为 $y\to x$；$s\neq mask_j$ 则说明初始方向为 $x\to y$。

然后还需要找到 $x$ 结点的邻居 $y$。对所有满足 $s_i=0$ 的询问此时边的方向为 $y\to x$ 因此必然满足 $f_{i,x}=f_{i,y}+w_{i,x}$。所以直接枚举所有还没有被删除的结点 $y$ 查询整个等式是否对所有 $s_i=0$ 的询问都成立即可。这个东西判断错误的概率极低。

确定 $y$ 后把 $x$ 结点的信息在树上删除即可。对第 $i$ 次询问如果此时边的方向为 $x\to y$ 也就是 $s_i=1$ 那么原来能够到达 $x$ 的 $w_{i,x}$ 个结点都能够继续到达 $y$，更新 $w_{i,y}\leftarrow w_{i,y}+w_{i,x}$。否则不需要过呢更新。

时间复杂度最坏为 $O(kn^2)$ 其中 $k$ 是询问次数，这里取 $k=50$。 :::