【换根DP】Tree
感觉树形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;
}
还没有评论,来说两句吧...