支配树：在 (O(nlog n)) 时间内求出一张有向图中能切断一个点到起点的所有路径的点
具体地，先定义一个起点 (S)（要求它能到达所有点），对于图中一个点 (u)，存在一些点 (v)，使得删去某个 (v) 后 (S) 无法走到 (u)，这些点 (v) 所组成的集合就是支配树上 (u) 到根的路径。特别地，(u) 的父亲就是离它最近的支配点。
一个很重要的性质：对于任意点 (u)，如果 (x) 支配 (u) 且 (y) 支配 (u)，则 (x) 与 (y) 之间存在支配关系。
证明显然。由此不难推出支配关系形成一棵树。
求支配树的方法：
1. DAG 上求支配树
按照拓扑序枚举所有点，对于一个点 (u)，所有能到达它的点的支配树已经求出， 于是我们枚举 (u) 的入点 (v)，找出它们在已求出的支配树上的 LCA，即为 (u) 的支配点（证明感性理解），然后将 (u) 加入支配树。
注意我们需要“动态”求这个 LCA，这问题不大，我们只需要每找到一个 (u) 的父亲时就立即更新它的倍增数组 fa[u][i] 即可。时间复杂度就 (O(nlog n))。
2. 一般图上求支配树
我们发现在 DAG 上很好做，考虑将一般图鼓捣成一个 DAG 且支配关系不变。
用著名的 Tarjan 思想，我们先搜出一棵 dfs 树再说。立即发现一个点 (u) 的支配点一定在它的dfs树的祖先中。
接下来，引入一个大家初学 Tarjan 就熟知的定理：对于有向图的 dfs 树而言，只存在前向边与反向边，不存在横叉边。
即只有祖先向孙子连边或孙子向祖先连边。
同样 DAG 部分，这次我们按dfs序逆序对每个点 (u) 考虑它的所有入点 (v)，维护一个“半支配点”(semi_u)。
分两种情况：
- (v) 为 (u) 的祖先。
此时 (v) 能一步走到 (u)，所以从 (v) 到 (u) 的路径上所有其它点都不可能成为 (u) 的支配点（否则压根切不断），所以 (u) 的真实支配点应该在 (v) 上方，故用 (v) 更新 (u) 的半支配点。（这里的更新指取 dfs 序最小的作为答案） - (v) 为 (u) 的子孙。
此时我们考虑 (u) 到 (v) 的路径上所有点 (w) 以及它们的半支配点 (semi_w)，发现如果我们割的点在任意一个 (semi_w) 下方，那么从根就可以走路径 (Srightarrow semi_wrightarrow wrightarrow vrightarrow u) 到达 (u)，矛盾。因此用所有 (w) 的半支配点 (semi_w) 更新 (u) 的半支配点 (semi_u)。
画个图理解一下：
更新完毕后，我们就得到了每个点 (u) 的“半支配点”。“半支配点”的本质意义在于，(u) 的真实支配点一定在它的半支配点到根的路径上。因此只保留 dfs 树上的边以及新加入的 (semi_urightarrow u) 的边，整张图的支配关系不变。
于是我们只保留原 dfs 树中的边，将其它边统统删掉，然后对于每个 (u) 加入边 (semi_urightarrow u)，在这个新的只有 (2(n-1)) 条边的 DAG 上跑做法 1 即可。
现在只剩下怎么快速对一个点 (v) 找出 (u) 到 (v) 的路径上所有 (w) 的 (semi_w) 的 dfs 序最小值的问题了。
考虑维护每个点 (v) 已访问的祖先中 (semi) 的最小值 (mn_v)，查询时恰好就是查询 (v) 的 (mn_v)（因为 (v) 的祖先中第一个未访问的点就是 (u)）。用并查集维护，每次访问完一个节点 (u) 就被其父亲 (fa_u) 合并即可。时间复杂度 (O(nalpha(n))) 或 (O(nlog n))（我们都懒得写按秩合并对吧）。
总时间复杂度 (O(nlog n))。
上一个封装好的代码：（注意代码中 (mn_u) 直接写成了 semi[u]，所以必须在访问完一个 (u) 之后立即将其加入新图中）
#include <bits/stdc++.h> #define For(i,a,b) for(int i=a;i<=b;i++) #define Rev(i,a,b) for(int i=a;i>=b;i--) #define Fin(file) freopen(file,"r",stdin) #define Fout(file) freopen(file,"w",stdout) using namespace std; const int N=2e5+5; typedef long long ll; class DominatorTree{ int n,dfn[N],raw[N],dfscnt,semi[N],fa[N],pa[N],ffa[N][18],dep[N],in[N]; vector<int> to[N],from[N],cp[N],cv[N]; void dfs(int u){ raw[dfn[u]=++dfscnt]=u; for(int v:to[u]) if(!dfn[v]) { cp[u].push_back(v); pa[v]=u; dfs(v); } } int getfa(int x){ if(x!=fa[x]) { int t=getfa(fa[x]); semi[x]=min(semi[x],semi[fa[x]]); fa[x]=t; } return fa[x]; } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); Rev(i,17,0) if(dep[ffa[x][i]]>=dep[y]) x=ffa[x][i]; if(x==y) return x; Rev(i,17,0) if(ffa[x][i]!=ffa[y][i]) { x=ffa[x][i]; y=ffa[y][i]; } return ffa[x][0]; } public: void init(int _n) { n=_n; } void add_edge(int x,int y) { to[x].push_back(y); from[y].push_back(x); } void solve(int* ans){ dfs(1); assert(dfscnt==n); For(i,1,n) { fa[i]=i; semi[i]=dfn[i]; } Rev(i,n,2){ int u=raw[i]; for(int w:from[u]) { getfa(w); semi[u]=min(semi[u],semi[w]); } fa[u]=pa[u]; cp[raw[semi[u]]].push_back(u); // Must do it right now! } For(u,1,n) for(int v:cp[u]) { cv[v].push_back(u); in[v]++; } static int q[N],h,t; h=t=0; q[t++]=1; while(h<t){ int u=q[h++]; ans[u]=0; for(int v:cv[u]) if(ans[u]==0) ans[u]=v; else ans[u]=lca(ans[u],v); dep[u]=dep[ffa[u][0]=ans[u]]+1; For(i,1,17) ffa[u][i]=ffa[ffa[u][i-1]][i-1]; for(int v:cp[u]) if((--in[v])==0) q[t++]=v; } } }T; int n,m,ans[N],siz[N]; vector<int> son[N]; void dfs(int u) { siz[u]=1; for(int v:son[u]) { dfs(v); siz[u]+=siz[v]; } } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; T.init(n); For(i,1,m) { int x,y; cin>>x>>y; T.add_edge(x,y); } T.solve(ans); // For(i,1,n) cerr<<ans[i]<<' '; cerr<<endl; For(i,2,n) son[ans[i]].push_back(i); dfs(1); For(i,1,n) cout<<siz[i]<<' '; cout<<endl; cerr<<"Time = "<<clock()<<" msn"; return 0; } // START TYPING IF YOU DON'T KNOW WHAT TO DO 
