//对于每一个结点,是孩子+1的乘积 //因为自己一定会取,所以孩子的集合方案就多了一个空集 //换根dp过程,把原来的父节点旋转下去 //首先将父亲结点的方案数除以这个转上去的孩子+1 //也就是说消除原来这个孩子结点的贡献 //然后把新父亲结点乘以这个新孩子结点,也就是说贡献上去 //第二次dfs的过程中输出每个值 就完事了
换根dp的时候涉及到除法去除掉子树的贡献,要注意到考虑inv==0的情况,因为有可能某个孩子的dp值刚好是mod-1(贼坑!),这时候就得用其他孩子重新计算一遍dp值,每次深搜的时候直接计算ans数组就好了,不要去改变各个点的dp值,否则会引起错误。
//对于每一个结点,是孩子+1的乘积 //因为自己一定会取,所以孩子的集合方案就多了一个空集 //换根dp过程,把原来的父节点旋转下去 //首先将父亲结点的方案数除以这个转上去的孩子+1 //也就是说消除原来这个孩子结点的贡献 //然后把新父亲结点乘以这个新孩子结点,也就是说贡献上去 //第二次dfs的过程中输出每个值 就完事了 #include <bits/stdc++.h> using namespace std; #define ll long long const int N=1000100; const ll mod=1e9+7; int n; struct node { int v,next; }e[N<<1]; int head[N]; int cnt=0; ll dp[N]; ll ans[N]; ll qpow(ll base,ll power) { ll res=1; while(power) { if(power&1) res=res*base%mod; power>>=1; base=base*base%mod; } return res; } void add(int u,int v) { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int u,int pre) { dp[u]=1; for(int i=head[u];i;i=e[i].next) { int to=e[i].v; if(to==pre) continue; dfs(to,u); dp[u]=dp[u]*(dp[to]+1)%mod; } } void dfs2(int u,int pre) { //cout<<u<<","<<pre<<":"<<dp[u]<<endl; for(int i=head[u];i;i=e[i].next) { int to=e[i].v; if(to==pre) continue; //dp[u]/=dp[to]+1; ll inv=qpow(dp[to]+1,mod-2); if(inv)//直接逆元 { ans[to]=(ans[u]*inv%mod+1)%mod*dp[to]%mod; } else{ ll tmp=1; for(int j=head[u];j;j=e[j].next) { int son=e[j].v; if(son==pre||son==to) continue; tmp=tmp*(dp[son]+1)%mod; } ans[to]=(tmp+1)*dp[to]%mod; } dfs2(to,u); //dp[to]/=dp[u]+1; //dp[to]=dp[to]*qpow(dp[u]+1,mod-2)%mod; //dp[u]=dp[u]*(dp[to]+1)%mod; } } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); if(u==v) continue; add(u,v); add(v,u); } dfs(1,1);ans[1]=dp[1]; dfs2(1,1); for(int i=1;i<=n;i++) { printf("%lld\n",ans[i]); } }