Description：

给定一个 $DAG$ ， $m$ 次询问。每次给定一个点集 $S$ ，问仅保留 $S$ 中的点时图中有多少条不同的路径。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 2\times 10^5$

Solution：

把所有边都看成无向边统计一下每个点的度数，然后对于一条边 $x\to y$ ，如果 $deg[x]<deg[y]$ ，那么就每次在 $x$ 的时候统计这条边的贡献，否则在 $y$ 统计这条边的贡献，那么在每个点处只会枚举度数比他大的点，那么每个点只会枚举不超过 $\sqrt m$ 个点，于是再暴力复杂度也是对的了。

Code：

没有代码