P8819 星战 galaxy 题解

· · 个人记录

赛时因为 T4 这题一眼没看，事后发现真的神仙。

简化题面后条件为：

  1. 所有点出度为 1。
  2. 从所有点走出去都能走到环上。

不难发现条件仅为判断所有点出度为 1，即判断是否是一个内向基环树森林。

再看操作：

  1. 删掉一条边 (u,v)
  2. 对于 u，将所有边 (t,u) 删掉。
  3. 加入之前被删掉的边 (u,v)
  4. 对于一个之前被执行 2 操作的 u，将那次操作删除的所有边 (t,u) 加入。

由于我们判断答案的时候，只关心每个点的出度是否为 1，于是可以给每个点 u 都随机一个很大的权值 w_u，并时刻维护 \sum\limits_{i=1}^{n}w_id_i，d_u 为 u 的出度。

那么如果 sum=\sum\limits_{i=1}^{n}w_id_i=\sum\limits_{i=1}^{n}d_i，那么有很大的概率使得所有点的出度都为 1。

由于权值的随机性，跑十次随机然后答案取个与就能过民间数据了。

对于维护 \sum\limits_{i=1}^{n}w_id_i，我们可以预处理 su_u 为一开始 u 所有沿着入边到达的点的权值和，vl_u 表示当前时刻 u 所有入边能到的点的权值和。接着分操作讨论即可：

  1. 对于操作一，会使 d_u 减一，令 sum 和 vl_v 减去 w_u 即可。
  2. 对于操作二，会使 u 的入度为 0，和令 u 入边到达的所有点出度减一，等同于让 sum 减去 vl_u，再把 vl_u 变为 0。
  3. 对于操作三，会使 d_u 加一，给 sum 和 vl_v 加上 w_u 即可。
  4. 对于操作四，会使 d_u 的入度回到初始状态，那么 sum 的变化量为 su_u-vl_u，那么给 sum 加上变化量并使 vl_u=su_u 即可。

复杂度 O(n)，带 10 倍常数（好像不用跑这么多次都能过？）

所以为什么我考场不看 T3 啊。