[PAT] A1090 Highest Price in Supply Chain

题目大意

给出供应链总人数、起始货源的价格、每次经销的涨幅；以及供应链中所有人的直接供应者的编号。求出最大价格和销售最大价格的销售者的人数。

思路

显然整个供应链可以看作一棵树。题目转化为给一棵树，在树根出货物的价格为p，然后每往下走一层，价格增加r%，求深度最大的结点的价格，以及这个价格的叶子结点个数。
用结构体存储结点，每个结点用变长数组存储它的下家。DFS遍历求出每个结点的深度；再经过一次循环找到最深深度和最深深度的结点个数（也可以放在遍历时求出）。最后计算价格即可。

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
#define MAX 100000
struct node {
	int level;
	vector<int>child;
};
node G[MAX];
void DFS(int v, int layer) {
	G[v].level = layer;
	for (int i = 0;i < G[v].child.size();i++)
		DFS(G[v].child[i], layer + 1);
}
int main() {
	int n, i, temp, s;
	double p, r;
	scanf("%d%lf%lf", &n, &p, &r);
	for (i = 0;i < n;i++) {
		scanf("%d", &temp);
		if (temp != -1)G[temp].child.push_back(i);
		else s = i;
	}
	DFS(s, 0);
	int maxLevel = 0, maxNum = 0;
	for (i = 0;i < n;i++) {
		if (G[i].level > maxLevel) {
			maxLevel = G[i].level;
			maxNum = 1;
		}
		else if (G[i].level == maxLevel)maxNum++;
	}
	for (i = 0;i < maxLevel;i++)p *= 1.0 + r / 100.0;
	printf("%.2lf %d", p, maxNum);
	return 0;
}