求hack NOIPT3
查看原帖
求hack NOIPT3
530349
天空即为极限楼主2022/11/26 21:10

思路是先缩边双,在树形DP

fi,0/1f_{i,0/1} 表示第 ii 个选/不选的方案数

fi,0=(2fson,1+2fson,0)×Aif_{i,0}=\prod(2f_{son,1}+2f_{son,0})\times A_i

fi,1=(2fson,0+fson,1)×Bif_{i,1}=\prod(2f_{son,0}+f_{son,1})\times B_i

AiA_i 表示第 ii 个边双不选点的方案数,即 2Ei2^{E_i}

BiB_i 表示第 ii 个边双选点的方案数,即 (2Vi1)×2Ei(2^{V_i}-1)\times2^{E_i}

答案是 froot,1+froot,02Ef_{root,1}+f_{root,0}-2^{E}

2022/11/26 21:10
加载中...