[HNOI2015]落忆枫音

DP 方案数

题面

给一DAG，问加上一条边后以$1$为起点的生成树的方案数。

解析

考虑到每个点父亲的唯一性，对于一个单纯的DAG，$ans=\prod_{i=1}^n in[i]$（$in[i]$表示$i$点的入度).
现在加了一条边$(x,y)$，有可能出现环，于是我们要减去有环的情况。设环上的点为$a_1,a_2...a_k$，于是该情况方案数为$\frac{ans}{\prod_{i=1}^kin[a_i]}$（即环上点父亲固定，其它点任选）。
怎么统计呢?
设$dp[i]$表示从$y$到$i$的路径上上面式子的值，则$dp[i]=\frac{1}{in[i]}\sum dp[j](j\in i的未统计的邻点）$（这就是一个累乘的过程)
我们可以建反向边，从$x$出发（这样能证明其为环），找到$y$后回溯返回$\frac{ans}{in[y]}$,否则返回$0$,最后答案在$dp[x]$里。
答案为$\prod_{i=1}^n in[i]-dp[x]$

il void dfs(re int u)
{
  if(vis[u]) return;vis[u]=1;
  if(u==y) {dp[u]=1ll*sum*ksm(in[u],mod-2)%mod;return;}
  for(re int i=h[u];i+1;i=e[i].next)
    {
      re int v=e[i].to;
      dfs(v);
      dp[u]=(dp[u]+dp[v])%mod;
    }
  dp[u]=1ll*dp[u]*ksm(in[u],mod-2)%mod;
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();x=gi();y=gi();
  fp(i,1,m)
    {
      re int u=gi(),v=gi();
      add(v,u);in[v]++;
    }
  ++in[1];//！！！！！！！
  fp(i,1,n)
    {
      if(i==y) ans=1ll*ans*(in[i]+1)%mod;
      else ans=1ll*ans*in[i]%mod;
      sum=1ll*in[i]*sum%mod;
    }
  dfs(x);
  printf("%lld\n",(1ll*mod+ans-dp[x])%mod);
  return 0;
}