【换根DP】Tree

r囧r小猫 2024-03-17 09:26 127阅读 0赞

感觉树形DP换根什么的全白学了

自己写都写不出来

555555555

题意:

c2f9ce51393f4076ba3486a465fb156d.png

思路:

我连以1为根的简单树形DP都没写出来

呃呃

1ea5d3fea9cf42c898fb96182799a4a3.png

Code:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define max(a,b) (a>b?a:b)
  4. #define min(a,b) (a<b?a:b)
  5. using i64 = long long;
  6. using namespace std;
  7. const int mxn=1e6+10;
  8. const int mxe=1e6+10;
  9. const int mod=1e9+7;
  10. struct ty{
  11. int to,next;
  12. }edge[mxe<<2];
  13. int N,u,v,tot=0;
  14. int head[mxn],dp[mxn],dp2[mxn];
  15. void add(int u,int v){
  16. edge[tot].to=v;
  17. edge[tot].next=head[u];
  18. head[u]=tot++;
  19. }
  20. void G_init(){
  21. tot=0;
  22. for(int i=0;i<=N;i++){
  23. head[i]=-1;
  24. }
  25. }
  26. int ksm(int a,int b,int mod){
  27. int res=1;
  28. while(b){
  29. if(b&1) res=(res*a)%mod;
  30. a=(a*a)%mod;
  31. b>>=1;
  32. }
  33. return res;
  34. }
  35. void dfs1(int u,int fa){
  36. dp[u]=1;
  37. for(int i=head[u];~i;i=edge[i].next){
  38. if(edge[i].to==fa) continue;
  39. dfs1(edge[i].to,u);
  40. dp[u]=dp[u]*(dp[edge[i].to]+1)%mod;
  41. }
  42. }
  43. void dfs2(int u,int fa){
  44. if(fa==0) dp2[u]=dp[u];
  45. else if((dp[u]+1)%mod==0){
  46. dfs1(u,u);
  47. dp2[u]=dp[u];
  48. }else{
  49. dp2[u]=(dp2[fa]%mod*ksm(dp[u]+1,mod-2,mod)+1)%mod*dp[u]%mod;
  50. }
  51. for(int i=head[u];~i;i=edge[i].next){
  52. if(edge[i].to==fa) continue;
  53. dfs2(edge[i].to,u);
  54. }
  55. }
  56. void solve(){
  57. cin>>N;
  58. G_init();
  59. for(int i=1;i<=N-1;i++){
  60. cin>>u>>v;
  61. add(u,v);
  62. add(v,u);
  63. }
  64. dfs1(1,0);
  65. dfs2(1,0);
  66. for(int i=1;i<=N;i++) cout<<dp2[i]<<'\n';
  67. }
  68. signed main(){
  69. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  70. int __=1;//cin>>__;
  71. while(__--)solve();return 0;
  72. }

发表评论

表情:
评论列表 (有 0 条评论,127人围观)

还没有评论,来说两句吧...

相关阅读