[CF 543D] Road Improvement

作法：

首先容易得出以某個點為根的算法：如果記每個點的子樹的取法數為 $dp[ x ]$ ，那麼 $dp[ x ] =\prod  ( dp[ s ] + 1 )$ ，其中$s$跑遍所有$x$的子節點。而當我們算出整棵樹以 $x$ 為根時每個點的 $dp$ 值了，如果現在想要轉移到整棵樹以某個 $x$ 的子節點 $s$ 的 $dp$ 值，那麼其實會變動的 $dp$ 值只有兩個，也就是$x$和$s$的值，並且不難知道他們新的 $dp$ 值的算法，因此只要再對原圖做一次 DFS ，每次要往下走時把 $dp$ 值更新成以他為根時的所有點的 $dp$ 值，走回來時再把 $dp$ 值還原就可以了。

但這樣有個很不明顯的陷阱，就是當在換根的時候 $dp[ x ]$ 的新的值會是 $\frac{dp[ x ]}{dp[ s ] + 1} $，因此如果$dp[ x ]$和$dp[ s ] + 1$都是$MOD $的倍數，那麼就不知道新的 $dp$ 值到底是多少了！因此只好對於每個 $dp$ 值，都紀錄一個「這個數是 $MOD$ 的幾次方的倍數」才可以正確的計算 $dp$ 值。

code :

#include<bits/stdc++.h>
#define MOD 1000000007
#define LL long long
using namespace std;
const int maxn=200000+10 ;
 
LL power(LL x,int n)
{
    if(n<=1) return n ? x : 1LL ;
    LL tmp=power(x,n/2) ;
    if(n%2) return (tmp*tmp%MOD)*x%MOD ;
    else return tmp*tmp%MOD ;
}
 
LL inv(int x)
{
    return power(x,MOD-2) ;
}
 
struct LL2
{
    int pow ; LL x ;
    LL get()
    {
        return pow ? 0LL : x ;
    }
    LL2 operator * (const LL2 &rhs) const
    {
        return (LL2){pow+rhs.pow,x*rhs.x%MOD} ;
    }
    LL2 operator / (const LL2 &rhs) const
    {
        return (LL2){pow-rhs.pow,x*inv(rhs.x)%MOD} ;
    }
};
 
LL2 add1(LL2 p)
{
    if(p.pow) return (LL2){0,1} ;
    else if(p.x+1==MOD) return (LL2){1,1} ;
    else return (LL2){0,p.x+1} ;
}
 
LL2 ans[maxn],dp[maxn] ;
vector<int> v[maxn] ;
void dfs(int x,int f)
{
    dp[x]=(LL2){0,1} ;
    for(auto i : v[x]) if(i!=f)
        dfs(i,x) ,
        dp[x]=dp[x]*add1(dp[i]) ;
}
 
void dfs2(int x,int f)
{
    ans[x]=dp[x] ;
    LL2 tmp=dp[x] ;
    for(auto i : v[x]) if(i!=f)
    {
        LL2 tmp2=dp[i] ;
        dp[x]=dp[x]/add1(dp[i]) ;
        dp[i]=dp[i]*add1(dp[x]) ;
        dfs2(i,x) ;
        dp[x]=tmp ; dp[i]=tmp2 ;
    }
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=2;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        v[i].push_back(x) ;
        v[x].push_back(i) ;
    }
    dfs(1,-1) ;
    dfs2(1,-1) ;
    for(int i=1;i<=n;i++) printf("%I64d%c",ans[i].pow?0:ans[i].x,i==n?'\n':' ') ;
}