AtCoder Beginner Contest 133 E - Virus Tree 2(组合数学)

AtCoder Beginner Contest 133 E - Virus Tree 2(组合数学)

​

题意：

思路：

代码：

const int maxn=3e5+7,mod=1e9+7,inf=0x3f3f3f3f;int n,k,dp[maxn];vectorg[maxn];void dfs(int u,int fa){ int las=0; for(auto t:g[u]){ if(t==fa) continue; if(las) dp[t]=las-1; else if(!fa) dp[t]=k-1; else dp[t]=k-2; las=dp[t]; } for(auto t:g[u]){ if(t!=fa) dfs(t,u); }}int main(){ n=read,k=read; rep(i,1,n-1){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } dp[1]=k; dfs(1,0); ll ans=1; rep(i,1,n) ans=ans*dp[i]%mod; write(ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。