//对于每一个结点,是孩子+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]);
}
}


京公网安备 11010502036488号