题解
1.具体去考虑每个集合所包含的元素及其大小个数是非常繁琐的,所以我们考虑每个元素对答案的贡献
2.
令 \(f[now]\) 代表以 \(now\) 为根节点的答案
\(sizes[now]\) 代表以 \(now\) 为根节点所包含集合的个数
更新过程如下:
\(f[now]+=f[next]*(sizes[now]+1)+f[now]*sizes[next]\)
\(size[now]+=sizes[next]*(sizes[now]+1)\)
最后 \(f[now]+=a[now],sizes[next]++\)
就像往一颗已知树插入子树的过程
code
#define ll long long
#include<bits/stdc++.h>
using namespace std;
const ll mod=1e8+7;
ll f[1000006]={0},sizes[1000006]={0};
vector<ll> G[1000006];
ll k,n;
void dfs(ll now,ll fa)
{
for(auto next:G[now])
{
if(next==fa) continue;
dfs(next,now);
f[now]=(f[now]+f[next]*(sizes[now]+1)%mod)%mod+f[now]*(sizes[next])%mod;
sizes[now]+=sizes[next]*(sizes[now]+1)%mod;
f[now]%=mod;
sizes[now]%=mod;
}
f[now]+=(k?now:1);
f[now]%=mod;
sizes[now]++;
sizes[now]%=mod;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
for(ll i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
G[x].emplace_back(y);
G[y].emplace_back(x);
}
dfs(1,1);
cout<<f[1];
return 0;
}
标签:疑惑,sizes,ll,dfs,next,P5007,now,DDOSvoid,mod
From: https://www.cnblogs.com/pure4knowledge/p/18094323