分析
首先这道题在出题人没有专门卡的情况下
是一道超级简单题。。。
当以1为根时,转移如下
那么我们考虑换根DP
每次只需要除以转移到的儿子在当前节点的贡献即可
即乘逆元即可转移成功
本题是有DP[x]=Mod-1的数据的
而没有逆元
所以
我们需要换一种方法换根
因为我们要排除当前儿子节点的贡献
只算上两侧节点
所以我们考虑维护前缀积和后缀积
即可
详情见代码
代码
//CF543D
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f3f3f3f3f
#define Mod 1000000007
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=2e5+10;
LL Ans[MaxN],Son[MaxN];
LL G[MaxN],F[MaxN]={0,1};
vector<LL>Pre[MaxN],Suf[MaxN];
LL Total,u,v;
LL Next[MaxN<<1],End[MaxN<<1],Head[MaxN],Cur;
inline void File() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
inline void Add_Edge(LL From,LL To) {
Next[++Cur]=Head[From];
Head[From]=Cur;
End[Cur]=To;
}
inline void DFS_one(LL New,LL Fa) {
G[New]=1;
Pre[New].push_back(1LL);
Suf[New].push_back(1LL);
for(LL i=Head[New];i;i=Next[i]) {
if(End[i]==Fa) continue;
DFS_one(End[i],New);
(G[New]*=(G[End[i]]+1))%=Mod;
Son[New]++;
Pre[New].push_back(G[End[i]]+1);
Suf[New].push_back(G[End[i]]+1);
}
Pre[New].push_back(1LL); Suf[New].push_back(1LL);
FOR(i,1,Son[New]) { (Pre[New][i]*=Pre[New][i-1])%=Mod; }
BOR(i,Son[New],1) { (Suf[New][i]*=Suf[New][i+1])%=Mod; }
}
inline void DFS_two(LL New,LL Fa) {
for(LL i=Head[New],Cnt=1;i;i=Next[i],Cnt++) {
if(End[i]==Fa) continue;
LL Temp=(New==1 ? 1 : F[New]);
F[End[i]]=(Temp*(Pre[New][Cnt-1]*Suf[New][Cnt+1]%Mod)%Mod+1)%Mod;
DFS_two(End[i],New);
}
}
inline LL Fast(LL A,LL B) {
LL Res=1;
A%=Mod;
while(B) {
if(B & 1) { Res=(Res*A)%Mod; }
A=(A*A)%Mod; B>>=1;
}
return Res%Mod;
}
signed main() {
// File();
ios::sync_with_stdio(false);
cin>>Total;
FOR(i,2,Total) { cin>>u; Add_Edge(u,i); Add_Edge(i,u); }
DFS_one(1,0);
// FOR(i,1,Total) { cout<<"i: "<<i<<" DP[i]: "<<DP[i]<<endl; }
DFS_two(1,0);
cout<<G[1]%Mod<<" ";
FOR(i,2,Total) cout<<G[i]*F[i]%Mod<<" ";
Skip;
// fclose(stdin);
// fclose(stdout);
// system("pause");
return 0;
} 
京公网安备 11010502036488号