个人练习-PAT甲级-1090 Highest Price in Supply Chain

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805376476626944

和【1079 Total Sales of Supply Chain】（解题报告https://blog.csdn.net/Rstln/article/details/120220246?spm=1001.2014.3001.5502）是同源题，基本上没差别，就是树的DFS，找到最深的叶子深度和最深叶子的数量。

用isParent[]数组记录节点是叶子还是非叶节点，仅对叶子节点自底向上DFS，用lvl[]数组记录层数。基本和1079题一样。

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;int getLvl(int nxt, vector<int>& parent, vector<int>& lvl) {
    if (nxt < 0)return -1;if (parent[nxt] >= 0 && lvl[parent[nxt]] >= 0)lvl[nxt] = lvl[parent[nxt]] + 1;elselvl[nxt] = getLvl(parent[nxt], parent, lvl) + 1;return lvl[nxt];
}int main() {
    int N;double P, r;scanf("%d %lf %lf", &N, &P, &r);vector<int> parent(N, -1);vector<bool> isParent(N, false);vector<int> lvl(N, -1);lvl[0] = 0;for (int i = 0; i < N; i++) {
    int K;scanf("%d", &K);parent[i] = K;if (K >= 0)isParent[K] = true;}double ret = 0.0;int num_r = 0;for (int i = 0; i < N; i++) {
    if (!isParent[i]) {
    lvl[i] = 0;double sale =  P;int nxt = parent[i];while (nxt != -1) {
    if (lvl[nxt] >= 0) {
    sale *= pow((1 + r / 100.0), lvl[nxt] + 1);break;}elsegetLvl(nxt, parent, lvl);}if (sale > ret) {
    ret = sale;num_r = 1;}else if (sale == ret)num_r++;else;}}printf("%.2f %d", ret, num_r);return 0;
}