题解：

考虑dp[u][0/1]表示u的子树中有没有坏边的方案数，

dp[u][0] = 1(显然必须全是好边)

dp[u][1] = ∏ (dp[v][0] * 2 + dp[v][1]) - 1 (-1是全是好边的情况)

然后我们考虑这个dp[u][0]并没有必要单独设出来

令f[u] = dp[u][0] + dp[u][1]

则f[u] = ∏ (1 + f[v])

显然f[1]可以求出来了

这个就是ans[1]

然后再扫一遍，记录从根到u的信息val = ans[u] / (1 + f[v])

这样ans[v] = f[u] * (val + 1)（将来自父亲的那一块也看成子树）

然后这里 /（1 + f[v]）求逆元是错的

因为 1 + f[v] == mod 时就GG了

所以考虑维护前缀和、后缀和

每次乘一下就可以了

1 #include
      
        2 #define ll long long 3 #define maxn 200005 4 using namespace std; 5 const ll mod = 1000000007; 6 int n; 7 vector
       
         g[maxn]; 8 ll f[maxn],ans[maxn]; 9 ll fastpow(ll a,ll p)10 {11     ll res=1;12     while(p)13     {14         if(p&1)res=res*a%mod;15         a=a*a%mod;p>>=1;16     }17     return res;18 }19 ll inv(ll x)20 {21     return fastpow(x,mod-2);22 }23 void dfs(int u)24 {25     f[u]=1;26     for(int i=0;i
        
          pre(sz+1,0),suf(sz+1,0);39     pre[0]=1,suf[sz]=1;40     for(int i=1;i<=sz;++i)41     {42         int v=g[u][i-1];43         pre[i]=pre[i-1]*(1+f[v])%mod;44     }45     for(int i=sz-1;i>=0;--i)46     {47         int v=g[u][i];48         suf[i]=suf[i+1]*(1+f[v])%mod;49     }50     for(int i=0;i