P5007 但模数的疑惑
xinxin2022
·
·
题解
省流：\bmod\ 10^8+7。
现有题解好像都没有认真讲转移式怎么来的，我来写一下。
显然设 f_u 为子树内价值和，w_u 为 u 的点权，由于需要知道集合数才能转移，再设 g_u 为子树内集合数。
- 已考虑的子树和目前子树内所有集合组合：$f_u\times g_v$。
- 已考虑的子树内所有集合和目前子树组合：$g_u\times f_v$。
- 不取目前子树集合：$f_u$。
- 只取目前子树集合：$f_v$。
- 综上：$f_u\to f_u\times g_v+g_u\times f_v+f_u+f_v$。
$g_u$ 的转移：
- 已考虑的子树内所有集合和目前子树集合组合 $g_u\times g_v$。
- 不取目前子树集合：$g_u$。
- 只取目前子树集合：$g_v$。
- 综上：$g_u\to g_u\times g_v+g_u+g_v$。
注意到只取 $u$ 也是一种情况，在最后令 $f_u\to f_u+w_u,g_u\to g_u+1$ 即可。
答案显然为 $f_1$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5,mod=1e9+7;
int n,t,u,v;
ll f[N],g[N],w[N];
vector<int> G[N];
void dfs(int u,int fa){
for(int v:G[u]){
if(v==fa) continue;
dfs(v,u);
f[u]=(f[u]*g[v]+f[v]*g[u]+f[u]+f[v])%mod;
g[u]=(g[u]*g[v]+g[u]+g[v])%mod;
}
(f[u]+=w[u])%mod;
g[u]++;
}
int main(){
cin>>n>>t;
for(int i=1;i<n;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)
w[i]=t*(i-1)+1;
dfs(1,1);
cout<<f[1];
return 0;
}
```