【BZOJ4011】【HNOI2015】落忆枫音

首先显然若是像没加边之前一样是一个DAG的话,那么答案显然为每个点的入度之积,即每个点选择一个父亲。

如果新加的边是指向\(1\)的那么这条边没用。

否则加了一条边之后可能会出一些问题。就是可能最后会选出来一个环。

那么显然环是包含新加的这条边的。所以就是找到所有对应的从\(y\)到\(x\)的路径。

答案为\(\prod{d}-\sum_{一条y到x的路径}\prod{d_j}\),其中\(j\)不在路径上。

令\(dp_i=\sum_{一条y到i的路径}\prod{d_j}\),其中\(j\)不在路径上。

那么转移就很简单了。

说点什么

您将是第一位评论人!

提醒
wpDiscuz