AcWing 1580. 供应链最高价格
原题链接
简单
作者:
Laity_3
,
2021-08-20 17:48:16
,
所有人可见
,
阅读 248
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, cnt;
int e[N];
vector<int> ne[N];
int max_depth;
int dfs(int root, int depth,int& max_depth) {
if (max_depth < depth) {
max_depth = depth;
}
if (!ne[root].size())return depth;
for (int i = 0; i < ne[root].size(); i++) {
dfs(ne[root][i], depth + 1,max_depth);
}
return depth;
}
int dfs1(int root, int max_depth, int depth,int& cnt) {
if (depth== max_depth) {
cnt++;
}
if (!ne[root].size())return depth;
for (int i = 0; i < ne[root].size(); i++) {
dfs1(ne[root][i], max_depth, depth+1,cnt);
}
return depth;
}
int main() {
cin >> n;
double price, profit;
cin >> price >> profit;
int root = 0;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
ne[num].push_back(i);
if (num == -1)
root = i;
}
int depth = 0;
max_depth = 0;
dfs(root, depth,max_depth);
dfs1(root, max_depth, depth, cnt);
profit /= 100;
for (int i = 0; i < max_depth; i++) {
price *= (1 + profit);
}
printf("%.2f ", price);
cout << cnt;
}