L2-020 功夫传人 (25 分)

(DFS)水题~。

注意边界(case)：只有一个节点且是得道者。

const int N=1e5+10;
vector<int> g[N];
double expand[N];
int n;
double m,r;
double sum;

void dfs(int u,double power)
{
    if(expand[u]) sum+=power*expand[u];
    for(int i=0;i<g[u].size();i++)
    {
        int j=g[u][i];
        dfs(j,power*(1-r/100));
    }
}

int main()
{
    cin>>n>>m>>r;

    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        if(k == 0) cin>>expand[i];
        else
        {
            for(int j=0;j<k;j++)
            {
                int x;
                cin>>x;
                g[i].pb(x);
            }
        }
    }

    dfs(0,m);
    cout<<int(sum)<<endl;
    //system("pause");
    return 0;
}