题目

 

题目大意

一个供应链由供应商、经销商、零售商组成。供应商作为根节点，售卖价格为P的商品，每经过一级经销商或零售商都会以高于r%的价格批发或出售。题目给出总节点数n，每个节点的编号从0到n-1，给出的每个值是该节点编号的索引，也就是父。求商品的最大价格和售卖最大价格商品的零售商的个数。

思路

"each number Si is the index of the supplier for the i-th member"每个Si是第i个成员的供应商的索引，也就是说，Si是i的父节点。例如第一个数1，其索引为0，1是0的父节点，相当于知道父节点和它的孩子节点的信息，那么在接收输入的时候就可以将这个树用二维数组表示出来，一个维度表示根节点，另一个维度开一个数组表示孩子节点。

求树的深度当然要dfs，递归参数毫无疑问是根节点和递归深度。当遍历到叶子节点时就能return，在return前处理深度maxnum，和最大个数maxsize。maxnum比较简单，只要一直取当前递归深度和maxnum的最大值就可以了。但maxsize需要注意取的是最深层的节点个数，不是整个树的最大宽度，所以还要判断当前是否位于最大层。如果当前正处于最大层，说明遍历到了处于最大层的另一个叶子节点，maxnum++，如果遍历到了比最大层还要深的层，那么更新最大层，将maxnum重置为1。

代码

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;vector<int> v[100003];
int maxn = 0, maxs = 0;  // 最大层数/深度，最大层对应的叶子节点个数void dfs(int root, int num){  // 根节点，当前深度if ((int)v[root].size() == 0){if (num == maxn){maxs++;  // 找到了另一个最大深度的叶子节点}else if (num > maxn){maxn = num;maxs = 1;  // 找到了一个更大深度的叶子节点}return;}else{for (int i = 0; i < (int)v[root].size(); i++){dfs(v[root][i], num + 1);}}
}  // 递归找最大深度和最大深度对应的节点个数int main(){int n;double p, r;cin >> n >> p >> r;int root;for (int i = 0; i < n; i++){int k;cin >> k;if (k == -1){root = i;}else{v[k].push_back(i);}}  // v既可以看成一维数组，又可看成二维数组。用二维数组来表示树dfs(root, 0);double res = p * pow(1 + r * 0.01, maxn);printf("%.2lf %d\n", res, maxs);return 0;
}