自己瞎胡的支配树，可能是错的（大雾
首先我们可以证明，支配关系成树。考虑一个点 \(x\) 的两个受支配点 \(y,z\)，这两个点应该在一条路径上，如果 \(y,z\) 之间没有支配关系，那么 \(y\) 应该存在一条不过 \(z\) 的路径，而这条路径接着走到 \(x\) 与 \(z\) 支配 \(x\) 矛盾，因此不存在这样的两个点 \(y,z\)，支配关系成树。
方便起见我们可以将这样的树建出来，只需要枚举每个点删掉，BFS 求出每个点的支配集，然后再对支配集拓扑排序即可。
再考虑加上这么一条 \(x\to y\) 边之后的变化。这样加边显然只会影响到 \(LCA(x,y)\) 子树内的点的受支配集，并且 \(x\) 子树内是不会影响到的。受影响的点应该从 \(y\) 可达，所以可以从 \(y\) 开始 BFS。当我们遍历到一个点的时候，如果这个点不在 \(LCA(x,y)\) 子树内，不计入答案，但是仍然让它往下搜，因为可能又走回到子树内影响某些点的受支配集。而当我们走到 \(LCA(x,y)\) 或者父亲节点是 \(LCA(x,y)\) 的时候，就不能搜下去了，因为如果只在这里被遍历到，那么受支配集没有改变，还是 \(LCA(x,y)\) 以及一个儿子。
按照上面的过程模拟即可，时间复杂度 \(O(n^2+nq)\)。
标签：支配,P7520,子树内,省选,BFS,成树,LCA,联考 From： https://www.cnblogs.com/275307894a/p/17253181.html