BZOJ2815 [ZJOI2012] 灾难

2018 年 04 月 13 日发布.

Description

$n$ 个点 $m$ 条边的DAG，对于每个点，求它的重要度。重要度定义如下：

对于 $v$ 这个点，将其（和其相连的所有边）删去。之后考察所有点，如果某个点初始时出度不为 $0$ 而当前出度为 $0$ ，则将这个点也删去。重复这个过程直到没有点被删去。 $v$ 的重要度即为除它以外删掉的点的个数。

$n\leqslant10^5$ 。

Solution

首先我们把所有边都反向（这样比较方便处理，其实也无所谓的）。

这样的话，拓扑序后面的点不会影响到前面的点。

首先，我们有一个性质： $u$ 会影响到 $v$ 当且仅当所有从生产者到 $v$ 的路径上都包含 $u$ 。这是显然的。

对于一个点 $v$ ，找到会影响到它的点（也就是说，那些删掉之后会导致 $v$ 消失）中除了它本身外拓扑序最靠后的一个点，假设它是 $t_v$ 。

那么有一个重要的性质：会影响到 $v$ 的点只有 $v, t_v, t_{t_v}, ...$ 这些。

证明：

如果有某个点 $u$ 会影响到 $v$ ，它在拓扑序上必定位于某个 $t_k$ 和 $k$ 之间，其中 $k=t_{\ddots_v}$ 。

既然 $t_k$ 是最后一个能影响到 $k$ 的，那么 $u$ 就不能影响到 $k$ 。那么一定存在一条从生产者到 $k$ 的路径不经过 $u$ 。但是既然 $k$ 会影响到 $v$ ，就一定存在一条 $k$ 到 $v$ 的路径。把这两条路径拼起来，就能得到一条从生产者到 $v$ 、不经过 $u$ 的路径，于是 $u$ 就不能影响到 $v$ ，矛盾。

那么我们把 $t$ 当成父亲关系建出一棵树（即“灭绝树”），删掉 $v$ 之后受影响的结点个数就是 $v$ 的子树大小。所以现在只需要考虑 $t$ 怎么求。

按拓扑序建树，则考虑到某个点的时候它的前驱已经考虑完了。那么它的父亲就会是它所有的前驱的 LCA （因为只有删掉公共祖先才能使这些前驱都被删掉，从而使 v 被删掉）。

边建树边倍增即可。复杂度 $O(n\log n)$ 。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>

const int N = 100050;
const int M = 1000050;

int pre[N], to[M], nxt[M], cnt;
int n, m, f[N], fa[N][20], dep[N], ind[N];
int que[N], siz[N];

inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
}

int LCA(int x, int y) {
  if (dep[x] < dep[y]) std::swap(x, y);
  for (int i = 19; i >= 0; --i)
    if (dep[fa[x][i]] >= dep[y])
      x = fa[x][i];
  for (int i = 19; i >= 0; --i)
    if (fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  return x == y ? x : f[x];
}

void Build(int x) {
  dep[x] = 1 + dep[fa[x][0] = f[x]];
  for (int i = 0; fa[x][i] != 0; ++i)
    fa[x][i + 1] = fa[fa[x][i]][i];
}

int main() {
  scanf("%d", &n);
  memset(pre, -1, sizeof pre);

  for (int x = 1; x <= n; ++x)
    for (int y; ; ) {
      scanf("%d", &y);
      if (y == 0) break;
      addEdge(y, x);
      ++ind[x];
    }

  int hd = 0, tl = 0;
  memset(f, -1, sizeof f);
  for (int i = 1; i <= n; ++i)
    if (ind[i] == 0) {
      dep[i] = 1;
      f[i] = 0;
      que[tl++] = i;
    }

  while (hd < tl) {
    int x = que[hd++];
    for (int i = pre[x]; i != -1; i = nxt[i]) {
      int y = to[i];
      if (f[y] == -1)
        f[y] = x;
      else if (f[y] != 0)
        f[y] = LCA(f[y], x);
      if ((--ind[y]) == 0)
        Build(que[tl++] = y);
    }
  }

  for (int i = n - 1; i >= 0; --i)
    siz[f[que[i]]] += ++siz[que[i]];
  for (int i = 1; i <= n; ++i)
    printf("%d\n", siz[i] - 1);
  return 0;
}