P2597 [ZJOI2012] 灾难（DAG上的支配树）

题目链接

所谓支配树，就是将关系转为一棵树，使得将树上点 \(x\) 单独去掉其祖先的任意一个，\(x\) 均不能选择，而非其父亲的点单独去掉对该点无影响。而其字树内的点则为去掉该点一定不能选择的点。

对于本题，如何建树？将原图连边（被吃的向捕食者连），拓扑排序，若当前点为 \(x\)，则其所有儿子都以其为食。

那么，对于一个点 \(v\)，当且仅当其所有父亲都不能选择时，该点不能选择。根据定义可得点 \(v\) 在支配树上的父亲为其在原树上的所有父亲的 lca。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ptc putchar
#define pb push_back
#define R(i, l, r) for (int i = l; i <= r; ++i)
#define debug puts("--------------------------------------------")
typedef long long ll;
typedef pair<int, int> PII;
namespace ZeroTwo
{
    template <typename T>
    il void read(T &x) 
    { 
        x = 0; T f = 1; char ch;
        while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
        x *= f;
    }
    template <typename T, typename ...L>
    il void read(T &x, L &...y) {read(x); read(y...);}
    template <typename T>
    il void write(T x) 
    {
        if (x < 0) ptc('-'), x = -x;
        if (x > 9) write(x / 10);
        ptc(x % 10 + '0');
    }
    template <typename T, typename ...L>
    il void write(T &x, L &...y) {write(x), ptc(' '); write(y...);}
}
using namespace ZeroTwo;
const int N = 65540;
int n, deg[N], a[N], f[N][25], dep[N], sz[N];
vector <int> E[N], G[N];
int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for (int i = 20; i >= 0; --i) 
    {
        if (k >= (1 << i)) k -= (1 << i), u = f[u][i];
        if (!k) break;
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; --i)
        if (f[u][i] ^ f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
void dfs(int x)
{
    sz[x] = 1;
    for (auto v : G[x]) 
    {
        dfs(v);
        sz[x] += sz[v];
    }
}
signed main() 
{
    cin >> n;
    R(i, 1, n)
    {
        a[i] = -1;
        int x;
        while (1)
        {
            cin >> x;
            if (!x) break;
            E[x].push_back(i);
            ++deg[i];
        }
    }
    queue <int> q;
    R(i, 1, n) if (!deg[i]) q.push(i), a[i] = 0;
    while (q.size())
    {
        int x = q.front(); q.pop();
        f[x][0] = a[x];
        dep[x] = dep[a[x]] + 1;
        G[a[x]].push_back(x);
        R(i, 1, 20) f[x][i] = f[f[x][i - 1]][i - 1];
        for (auto v : E[x])
        {
            if (a[v] == -1) a[v] = x;
            else a[v] = lca(a[v], x);
            --deg[v]; 
            if (!deg[v]) q.push(v);
        }
    }
    dfs(0);
    R(i, 1, n) cout << sz[i] - 1 << '\n';
    return 0;
}