更适合线性空间宝宝体质的 DAG 支配树

· · 题解

算法就是最典的那个，每个点在支配树上的父亲是前驱在支配树上的 LCA。直接把正常图的算法搬过来是能用的，或者 LCT 也不是不能做，但我们希望能用最简单的算法解决它。鉴于这是一篇题解，我们会首先介绍一下这个东西。

首先我们考虑把给定的捕食关系按照食物向捕食者的方向连边，同时从虚拟源点（太阳，0）向所有没有食物的点连边。这样整个图依然是一个 DAG，且生物 x 灭绝导致生物 y 当且仅当从 0 到 y 的每条路径都经过 x。这是显然的。对于这样的关系，我们称生物 y 支配生物 x。不难发现，只有当 y 能走到 x 时，y 有可能支配 x，且 0 能支配任何其他点。

不难发现，对于点 x,y,z，若 x 支配 z，y 能走到 z，且这三个点的拓扑序递增，则一定有 x 支配 y。证明就是一定不能存在一条太阳到 y 然后 y 到 z 的路不经过 x，而根据 DAG 上路径拓扑序的单调性第二段一定不会出现 x。

如此一来，对于一个节点 x，找到拓扑序最大的支配其的点 y。根据上面的性质，y 的拓扑序一定小于 x，且对于任意其他支配 x 的点 z，一定有 z 支配 y。不难发现，如果从 y 向 x 连边，这实际上构成了一棵以 0 为根的树，称之为“支配树”，而我们要求的即为每个点在支配树上的子树大小。

由于支配树的父子有拓扑偏序关系，我们考虑将节点按拓扑序从小到大排序。假设我们现在要处理点 x 并找到其在支配树上的父亲 y，考虑 x 的任一前驱 z，则若 y 的拓扑序小于 z，其一定支配 z；等于 z，其一定就是 z；大于 z，由于存在 0 到 z 到 x 的路径，其不符合支配的定义。换而言之，这样的 y 一定是每个 z 在支配树上的祖先。在此前提下，由于 y 支配（或等于）了 x 的每个前驱，不难发现其一定也支配 x，于是这个条件是充要的。由于我们要找拓扑序最大的 y，只需要对所有这些前驱求 LCA 即可。复杂度 O(n\log n)。

不难发现我们需要支持的是给一棵树动态加叶子和查 LCA，这是倍增的经典问题，使用 https://return20071007.blog.uoj.ac/blog/8981/ 中提到的神秘东西改写即可。

代码在这篇东西发出来之前是最优解。

#include <bits/stdc++.h>
using namespace std;
constexpr int S = 1 << 21, N = 65535;
char buf[S], *p1, *p2, obuf[S], *O = obuf;
inline char gc() {
  if (p1 == p2) {
    p2 = (p1 = buf) + cin.read(buf, S).gcount();
    if (p1 == p2) return EOF;
  }
  return *p1++;
}
inline int rd() {
  char ch;
  while (!isdigit(ch = gc()))
    ;
  int x = ch & 0xf;
  while (isdigit(ch = gc())) x = x * 10 + (ch & 0xf);
  return x;
}
inline void prtln(int x) {
  char s[7];
  int t = 0;
  if (!x)
    *O++ = '0';
  else {
    while (x) s[t++] = x % 10 | '0', x /= 10;
    while (t) *O++ = s[--t];
  }
  *O++ = '\n';
}
basic_string<int> es[N];
int n, fa[N], d[N], lb[N], dg[N], sz[N];
inline void lca(int& u, int v) {
  if (!~u) return u = v, void();
  if (d[u] < d[v]) swap(u, v);
  while (d[u] > d[v]) d[lb[u]] < d[v] ? (u = fa[u]) : (u = lb[u]);
  while (u != v)
    lb[u] == lb[v] ? (u = fa[u], v = fa[v]) : (u = lb[u], v = lb[v]);
}
inline void addf(int x) {
  int p = fa[x], q = lb[p], r = lb[q];
  d[x] = d[p] + 1, lb[x] = d[p] - d[q] != d[q] - d[r] ? p : r;
}
inline void build() {
  memset(fa + 1, -1, n * sizeof(int));
  int q[N], l = 0, r = 0, u;
  for (int i = 1; i <= n; ++i)
    if (!dg[i]) fa[q[r++] = i] = 0, d[i] = 1;
  while (l < r)
    for (addf(u = q[l++]); int v : es[u])
      if (lca(fa[v], u), !--dg[v]) q[r++] = v;
  while (r--)
    if (int f = fa[u = q[r]]) sz[f] += sz[u] + 1;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  n = rd();
  for (int i = 1; i <= n; ++i)
    while (int j = rd()) es[j].push_back(i), ++dg[i];
  build(), for_each_n(sz + 1, n, prtln);
  return cout.write(obuf, O - obuf).flush(), 0;
}