思路是先缩边双,在树形DP
fi,0/1f_{i,0/1}fi,0/1 表示第 iii 个选/不选的方案数
fi,0=∏(2fson,1+2fson,0)×Aif_{i,0}=\prod(2f_{son,1}+2f_{son,0})\times A_ifi,0=∏(2fson,1+2fson,0)×Ai
fi,1=∏(2fson,0+fson,1)×Bif_{i,1}=\prod(2f_{son,0}+f_{son,1})\times B_ifi,1=∏(2fson,0+fson,1)×Bi
AiA_iAi 表示第 iii 个边双不选点的方案数,即 2Ei2^{E_i}2Ei
BiB_iBi 表示第 iii 个边双选点的方案数,即 (2Vi−1)×2Ei(2^{V_i}-1)\times2^{E_i}(2Vi−1)×2Ei
答案是 froot,1+froot,0−2Ef_{root,1}+f_{root,0}-2^{E}froot,1+froot,0−2E