CF543D 题解
独立做出来了,开心。
考虑从 \(x\) 出发、到叶子的一条链,中间有了一条“不良的路”后,后面的边一定都是“改善的路”。
设 \(f_i\) 表示 \(i\) 的子树内的方案数,\(ans_i\) 表点 \(i\) 的答案。
\(f\) 利用乘法原理转移(儿子子树方案数相乘):
\[f_u=\prod_{v\in \operatorname{son}_u}(f_v+1)
\]
(加的那个 \(1\) 是不良道路正好在 \(u,v\) 间的情况。)
- 算出 \(f_u\) 后,\(ans\) 的转移(除掉 \(u\) 子树的贡献,得到点 u 子树外的答案,然后把结果转化为以 \(u\) 为根时的贡献,再把 \(u\) 子树乘回去):
\[ans_u=(\frac{ans_{fa}}{f_u+1}+1)\times f_u
\]
(把 \(\frac{ans_{fa}}{f_u+1}\) 加 \(1\) ,加的是不良道路正好在 \(u\) 和 \(fa\) 间的情况。)
但是做除法的话,可能出现 \(10^9+7\) 的倍数导致没有逆元而出错。所以考虑另一种统计方法。
求上面“点 \(u\) 子树外的答案”的时候出了问题,考虑重新表示这个东西,设 \(g_u\) 表示点 \(u\) 的子树以外的答案。
转移平凡,从 \(fa\) 到 \(u\),会多包含 \(u\) 的 \(brother\)。
\[g_u=g_{fa}\times\prod_{v\in\operatorname{brother}_u}(f_v+1)+1
\]
这个 \(+1\) 就是加的不良道路正好在 \(u\) 和 \(fa\) 间的情况。
前后缀积优化即可,记录所有儿子的 \(f_v+1\) 的前后缀积。
那么 \(ans\) 的转移中的 \(\frac{ans_{fa}}{f_u+1}+1\) 就换成 \(g_u\) 了。
双倍经验:AT dp_v,方程完全一样。
前者的“不良道路”可以理解为后者的“黑白点间的分界边”,只能有一条不良道路,就是说黑点互相联通,否则一条根叶路径上就有多条不良道路了。