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;
}
全部评论

相关推荐

10-27 17:26
东北大学 Java
点赞 评论 收藏
分享
3 收藏 评论
分享
牛客网
牛客企业服务