【换根DP】Tree-蒲公英云

【换根DP】Tree

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

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

自己写都写不出来

555555555

题意：

思路：

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

呃呃

Code：

#include <bits/stdc++.h>
#define int long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using i64 = long long;
using namespace std;
const int mxn=1e6+10;
const int mxe=1e6+10;
const int mod=1e9+7;
struct ty{
    int to,next;
}edge[mxe<<2];
int N,u,v,tot=0;
int head[mxn],dp[mxn],dp2[mxn];
void add(int u,int v){
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void G_init(){
    tot=0;
    for(int i=0;i<=N;i++){
        head[i]=-1;
    }
}
int ksm(int a,int b,int mod){
    int res=1;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void dfs1(int u,int fa){
    dp[u]=1;
    for(int i=head[u];~i;i=edge[i].next){
        if(edge[i].to==fa) continue;
        dfs1(edge[i].to,u);
        dp[u]=dp[u]*(dp[edge[i].to]+1)%mod;
    }
}
void dfs2(int u,int fa){
    if(fa==0) dp2[u]=dp[u];
    else if((dp[u]+1)%mod==0){
        dfs1(u,u);
        dp2[u]=dp[u];
    }else{
        dp2[u]=(dp2[fa]%mod*ksm(dp[u]+1,mod-2,mod)+1)%mod*dp[u]%mod;
    }
    for(int i=head[u];~i;i=edge[i].next){
        if(edge[i].to==fa) continue;
        dfs2(edge[i].to,u);
    }
}
void solve(){
    cin>>N;
    G_init();
    for(int i=1;i<=N-1;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=N;i++) cout<<dp2[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}