题目描述

题目大意：
供应链是由零售商，经销商和供应商构成的销售网络，现在，给定整个销售网络，请你计算零售商能达到的最高销售价格。

样例

9 1.80 1.00
1 5 4 4 -1 4 5 3 6

1.85 2

C++ 代码

要求最大价格，其实就是求这颗树的叶节点的最大树高maxh以及在这个高度下的叶节点数目cnt

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;
int N, root, maxh = 1, cnt = 0;
double p, r;
vector<int> child[maxn];

void dfs(int x, int h){
    if(child[x].size() == 0 && maxh < h){
        maxh = h;
        cnt=1;
    }
    else if(h == maxh) cnt++;

    for(int i = 0; i < child[x].size(); i ++ ){
        dfs(child[x][i], h+1);
    }
}

int main(){
    scanf("%d %lf %lf", &N, &p, &r);

    for(int i = 0; i < N; i ++ ){
        int temp;
        cin >> temp;
        if(temp == -1) root = i;
        else
            child[temp].push_back(i);
    }

    dfs(root, 1);
    //printf("%d %d", maxh, cnt);

    double ans = p*pow((1+r/100), maxh-1);  
    printf("%.2lf %d", ans, cnt);


return 0;
}