【PAT甲级】1090 Highest Price in Supply Chain (25 分)(DFS)

代码:

#include<bits/stdc++.h>
using namespace std;
int fa;
int degree[100007];
vector<int>v[100007];
void dfs(int x){
    for(auto&it:v[x]){
        degree[it]=degree[x]+1;
        dfs(it);
    }
    return;
}
double qpow(double x,int y){
    double ans=1,tmp=x;
    while(y){
        if(y&1)
            ans*=tmp;
        tmp*=tmp;
        y>>=1;
    }
    return ans;
}
int main(){
    int n;
    double p,r;
    scanf("%d%lf%lf",&n,&p,&r);
    int root=0;
    for(int i=0;i<n;++i){
        scanf("%d",&fa);
        if(fa==-1)
            root=i;
        else
            v[fa].push_back(i);
    }
    dfs(root);
    int mx=0;
    for(int i=0;i<n;++i)
        mx=max(mx,degree[i]);
    int num=0;
    for(int i=0;i<n;++i)
        if(degree[i]==mx)
            num++;
    double ans=p*qpow(1.0+r/100,mx);
    printf("%.2f %d",ans,num);
    return 0;
}

保持热爱 不懈努力 不试试看怎么知道会失败呢(划掉) 世上无难事 只要肯放弃(划掉)
原文地址:https://www.cnblogs.com/ldudxy/p/10827104.html