rt qwq

获得37分，貌似有的点直接找不到支配点

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pii pair<int ,int>
#define p1(x) x.first
#define p2(x) x.second
#define int long long
using namespace std;
int n,m;
vector<int>g[300300],ig[300300],dg[300300],hlf_dg[300300];
int dfn[300300],f[300300],fw[300300],fa[300300];
int loc[303000];
int hlf_dom[300300],siz[300300],dom[300300];
inline pii ff(int x){
    if(f[x]==x)return {x,0};
    pii e=ff(f[x]);
    f[x]=p1(e);
    if(dfn[fw[x]]>dfn[p2(e)])
    fw[x]=p2(e);
    return {f[x],fw[x]};
}
inline void merfa(int x){
    f[x]=fa[x];
    fw[x]=hlf_dom[x];
}
int tk;
inline void dfs(int u){
    loc[dfn[u]=++tk]=u;
    for(int v:g[u])
        if(!dfn[v])fa[v]=u,dfs(v);
}
inline void upd(int x,int y){
    if(dfn[y]<dfn[hlf_dom[x]])
        hlf_dom[x]=y;
}
inline bool cmp(pii A,pii B){return dfn[p2(A)]<dfn[p2(B)];}
inline void dfs_dom(int u){
    siz[u]=1;
    for(int v:dg[u])
    dfs_dom(v),siz[u]+=siz[v];
}
signed main(){
    // freopen("genshin.in","r",stdin);
    // freopen("genshin.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        ig[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        hlf_dom[i]=i,f[i]=i;
    dfn[0]=1e9;
    dfs(1);
    vector<pii>T;
    for(int i=n;i>=1;i--){
        int u=loc[i];

        for(int v:hlf_dg[u]){
            int p=p2(ff(v));
            if(!p)continue;
            if(hlf_dom[p]==u)dom[v]=u;
            else T.push_back({v,p});
        }

        for(int v:ig[u])
            if(dfn[v]<dfn[u])upd(u,v);
            else upd(u,hlf_dom[p2(ff(v))]);
        merfa(u);
        hlf_dg[hlf_dom[u]].push_back(u);
    }
    sort(T.begin(),T.end(),cmp);
    for(pii e:T)
        dom[p1(e)]=dom[p2(e)];
    for(int i=2;i<=n;i++)
        dg[dom[i]].push_back(i);
    dfs_dom(1);
    for(int i=1;i<=n;i++)
        cout<<siz[i]<<" ";
    return 0;
}