鏈接：https://ac.nowcoder.com/acm/problem/19782
題目：修修去年種下了一棵樹，現在它已經有n個結點了。
????????修修非常擅長數數，他很快就數出了包含每個點的連通點集的數量。
????????瀾瀾也想知道答案，但他不會數數，于是他把問題交給了你。

思路是很簡單的換根dp，先求出以1為根的值，然后進行撤回操作再換根，這里最要注意的坑點是 dp【v】+1%mod會等于0（加法會導致模等于0），所以我們這里需要特判處理。

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =1e6+10; const double eps = 1e-4; //const double pi=acos(-1); ll qk(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b/=2;}return ans%mod; } int n; ll dp[N]; vector<int> g[N]; ll w[N],f[N]; void dfs(int u,int f){dp[u]=1;for(int v:g[u]){if(v==f) continue;dfs(v,u);dp[u]=(dp[u]*((dp[v]+1ll)%mod))%mod;} } void DP(int u,int p){for(int v:g[u]){if(v==p) continue;if((dp[v]+1)%mod==0){if(p) f[v]=f[u]+1;else f[v]=1;for(int k:g[u]){if(k==v||k==p) continue;f[v]=(f[v]*(dp[k]+1)%mod)%mod;}}else f[v]=(w[u]*qk(dp[v]+1ll,mod-2))%mod;w[v]=(dp[v]*((f[v]+1ll)%mod))%mod;DP(v,u);} } void sovle(){cin>>n;for(int i=2;i<=n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);w[1]=dp[1];DP(1,0);for(int i=1;i<=n;i++) cout<<w[i]<<endl; } int main() { #ifdef LOCALfreopen("in.txt", "r", stdin); #elseint t=1;//cin>>t;while(t--) sovle(); #endif // LOCALreturn 0; }

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[牛客] Tree-换根dp（预防加法取模导致等0）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。