善于运用期望可加性+维护增量+DAG上dp：0912T4

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132857701

CP0912T4

首先看到无环，也就是DAG，显然拓扑

然后看到题目求类似期望和砍边的东西，就要考虑dp

然后有两个Trick

  1. 期望具有可加性

  2. 对于只有一次的操作，考虑增量

好了，现在我们考虑增量，假设已经知道不操作的答案，现在求恰好操作一次的增量

然后可以手玩一下，发现哪些边对哪些点会有哪些影响。

在这里插入图片描述

然后加起来就行了

1
2
3
4
5
f[v]=(f[v]+f[u]*iv[c[u]]%mo)%mo; 
g[v]=(g[v]+g[u]*iv[c[u]]%mo
	-f[u]*mp[u][v]%mo*iv[c[u]]%mo
	+f[u]*(s[u]-mp[u][v])%mo*iv[c[u]]%mo*iv[c[u]-1]%mo
	)%mo;