支配树咕了，太难了

Problem

DAG 上支配树

Solution

结论：
对于点 $v$ 若有边 $(u,v)$，则 $idom(v)=lca(idom(u))$。

此处 lca 指支配树上的 lca。

因此弄个超级源点，做一遍拓扑序求支配树 size 就行了 qwq

Code

// Code by ajcxsu
// Problem: disaster

#include<bits/stdc++.h>
using namespace std;

const int N=8e4+10, M=1e7+10, rt=N-1;
int h[N], h2[N], to[M], nexp[M], p=1;
int in[N];
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++, in[b]++; }
inline void ins2(int a, int b) { nexp[p]=h2[a], h2[a]=p, to[p]=b, p++; }

const int OP=18;
int gup[N][OP], l[N], dep[N];
int lca(int s, int t) {
    if(dep[s]<dep[t]) swap(s, t);
    for(int j=OP-1;j>=0;j--)
        if(dep[gup[s][j]]>=dep[t]) s=gup[s][j];
    if(s!=t) {
        for(int j=OP-1;j>=0;j--)
            if(gup[s][j]!=gup[t][j]) s=gup[s][j], t=gup[t][j];
        s=gup[s][0];
    }
    return s;
}

int siz[N];
void dfs(int x) {
    siz[x]=1;
    for(int u=h2[x];u;u=nexp[u])
        dfs(to[u]), siz[x]+=siz[to[u]];
}

int main() {
    ios::sync_with_stdio(false);
    int n, na;
    cin>>n;
    fill(dep+1, dep+N, 1);
    for(int i=1;i<=n;i++)
        while(cin>>na, na) ins(na, i);
    queue<int> qu;
    for(int i=1;i<=n;i++) if(!in[i]) ins(rt, i);
    qu.push(rt);
    int cnt=0;
    while(!qu.empty()) {
        na=qu.front(), qu.pop(), cnt++;
        for(int u=h[na];u;u=nexp[u]) {
            int v=to[u];
            in[v]--;
            if(!l[v]) l[v]=na;
            else l[v]=lca(na, l[v]);
            if(!in[v]) {
                dep[v]=dep[l[v]]+1, gup[v][0]=l[v];
                for(int j=1;j<OP;j++)
                    gup[v][j]=gup[gup[v][j-1]][j-1];
                ins2(l[v], v);
                qu.push(v);
            }
        }
    }
    dfs(rt);
    for(int i=1;i<=n;i++) cout<<siz[i]-1<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2597.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆