Road Improvement
Road Improvement
https://ac.nowcoder.com/acm/problem/110946
分析
首先这道题在出题人没有专门卡的情况下
是一道超级简单题。。。
当以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; }