Codeforces 543D Road Improvement

http://codeforces.com/contest/543/problem/D

题意：

给定n个点的树

问：

一开始全是黑边，对于以i为根时，把树边白染色，使得任意点走到根的路径上不超过一条黑边，输出染色的方案数(mod 1e9+7)

思路:得知f[x]=(f[s1]+1)*(f[s2]+1)*(f[s3]+1)..*(f[sn]+1）,s为x的儿子

因为要么这条边修了，里面有f[s1]方案，要吗不修，那剩下的都必须修。

由于要计算每个点的答案。

我们令up[x]为x父亲为x儿子时的f答案。可知up[x]=（fa的f前缀*fa的f后缀*up[fa]）+1

最后f[x]*up[x]就是答案。

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<vector>

#define ll long long

const ll Mod=;

int tot,go[],first[],next[],n;

ll up[];

ll f[];

std::vector<int>G[];

std::vector<ll>L[],R[];

int read(){

    int t=,f=;char ch=getchar();

    while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

    return t*f;

}

void dfs1(int x,int fa){

    f[x]=;

    for (int i=;i<G[x].size();i++){

        int pur=G[x][i];

        if (pur==fa){

            L[x].push_back();

            R[x].push_back();

            continue;

        }

        dfs1(pur,x);

        f[x]=(f[x]*(f[pur]+))%Mod;

        L[x].push_back(f[pur]+);

        R[x].push_back(f[pur]+);

    }

    for (int i=;i<L[x].size();i++)

     L[x][i]=(L[x][i]*L[x][i-])%Mod;

    for (int i=R[x].size()-;i>=;i--)

     R[x][i]=(R[x][i]*R[x][i+])%Mod;

}

void dfs2(int x,int fa,ll val){

    up[x]=val;

    ll tmp;

    for (int i=;i<G[x].size();i++){

        int pur=G[x][i];

        if (pur==fa) continue;

        tmp=val;

        if (i>) tmp=(tmp*L[x][i-])%Mod;

        if (i<G[x].size()-) tmp=(tmp*R[x][i+])%Mod;

        dfs2(pur,x,tmp+);

    }

}

void solve(){

    dfs1(,);

    up[]=;

    dfs2(,,1LL);

    for (int i=;i<=n;i++)

     printf("%I64d ",f[i]*up[i]%Mod);

}

int main(){

    n=read();for (int i=;i<=n;i++){int x=read();G[x].push_back(i);G[i].push_back(x);}

    solve();

}

巴特西

Codeforces 543D Road Improvement

最新文章

热门文章