题意：给出衣服有向无环图（DAG）,，定义出度为0的点为中心城市，每次询问给出两个点，求破坏任意一个城市，使得这两个点至少有一个点无法到达中心城市，求方案数。
思路：首先建立反向图，将城市到若干个终点看成从若干个起点出发到某个城市，再用一个源点连接那些度为0 的点，即可看成从源点出发到某个城市。要炸掉一个点使得无法到达某个城市，那么需要炸掉的是从源点到该城市的必经点，考虑建立支配树，根据定义可知支配树到根的链上结点个数就是必经点的个数。两个城市的容斥减去 LCA 到根上这条链即可。由于保证是 DAG ，因此直接按拓扑序建树即可，建完树利用结点的 depth 来求点到根的链长，注意最后答案要减去一开始添加的源点。
DAG支配树求法：先求拓扑序，按照拓扑序处理（建树）。对于一个点，所有能到达它的点在支配树中的lca，就是它支配树中的父亲。由于能到达他的点拓扑序必定比他本身小，所以肯定已经在建好的支配树上了，必定能求出lca。
现在还不会非DAG的支配树，学习博客为 https://wenku.baidu.com/view/b06471d019e8b8f67d1cb91b.html
#include<bits/stdc++.h> #define pb(a) push_back(a) #define clr(a) memset(a, 0, sizeof(a)) using namespace std; const int maxn = 1e5 + 5; vector<int >ve[maxn],rve[maxn]; int n,m,T; int deg[maxn],dep[maxn],id[maxn],tot; int f[maxn][20]; int rt=n+1; void bfs(){ rt=n+1; queue<int >q; for(int i=1;i<=n;i++){ if(!deg[i]){ q.push(i); ve[i].pb(rt); rve[rt].pb(i); } } while(!q.empty()){ int u=q.front(); q.pop(); id[++tot]=u; int si=rve[u].size(); for(int i=0;i<si;i++){ int v=rve[u][i]; if((--deg[v])==0){ q.push(v); } } } } int LCA(int x,int y){ if(dep[x]>dep[y])swap(x,y); for(int i=19;i>=0;i--){ if(dep[y]>dep[x]&&dep[x]<=dep[f[y][i]])y=f[y][i]; } for(int i=19;i>=0;i--){ if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; } return x==y?x:f[x][0]; } int main(){ cin>>T; while(T--){ cin>>n>>m; for(int i=1;i<=n+1;i++){ ve[i].clear(),rve[i].clear(); deg[i]=dep[i]=0; } tot=0; for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); ve[u].pb(v); rve[v].pb(u); deg[u]++; } bfs(); dep[rt]=1; for(int i=1;i<=n;i++){ int fa=-1; int u=id[i]; int si=ve[u].size(); for(int j=0;j<si;j++){ int v=ve[u][j]; fa=(fa==-1)?v:LCA(fa,v); } dep[u]=dep[fa]+1; f[u][0]=fa; for(int j=1;j<=19;j++){ f[u][j]=f[f[u][j-1]][j-1]; } } int q,u,v; cin>>q; while(q--){ scanf("%d%d",&u,&v); int lca=LCA(u,v); printf("%d ",dep[u]+dep[v]-dep[lca]-1); } } }