Pat grade a 1090 highest price in supply chain

A supply chain is a network of retailers（ Retailer ）, distributors（ Distributor ）, and suppliers（ supplier ）-- everyone involved in moving a product from supplier to customer.

Starting from one root supplier, everyone on the chain buys products from one's supplier in a price P and sell or distribute them in a price that is r% higher than P. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.

Now given a supply chain, you are supposed to tell the highest price we can expect from some retailers.

Input Specification:

Each input file contains one test case. For each case, The first line contains three positive numbers: N (≤105), the total number of the members in the supply chain (and hence they are numbered from 0 to N−1); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then the next line contains N numbers, each number Si​ is the index of the supplier for the i-th member. Sroot​ for the root supplier is defined to be −1. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the highest price we can expect from some retailers, accurate up to 2 decimal places, and the number of retailers that sell at the highest price. There must be one space between the two numbers. It is guaranteed that the price will not exceed 1010.

Sample Input:

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

Sample Output:

1.85 2

The question ：

         supplier （ The root node ） And dealers （ Child nodes of non leaf nodes ） And retailers （ leaf node ）, Form a supply chain , This supply chain is a tree , Every time we pass through a dealer and retailer, the price will rise r%, Give the number of nodes , The original price , And the percentage of price increase , The following line gives the dealer or supplier of each node （ The parent node ）, Ask the retailer to sell at the maximum price , There are several such prices ？

Ideas ：DFS Traverse every path , Compare and find out the maximum price , There is one such path, and the number is +1.

Code ：
 

// This number corresponds to the tree of the node , It is more convenient to build a tree statically with an array ; 
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int n,root,num=0,maxdepth=0,father;
double p,r;
const int maxn=1e5+10;
vector<int > node[maxn];// Store the subscripts of the parent node and its child nodes ;;

void DFS(int index, int depth){
	if(node[index].size()==0){// Reach the leaf node ,index As a parent node, there are no children , That is, leaf node , Complete the traversal of a route and judge once ; 
		if(depth>maxdepth){
			maxdepth=depth;
			num=1;
		}else if(depth==maxdepth){
			num++;
		}
		return ;
	}
	for(int i=0;i<node[index].size();i++){
		DFS(node[index][i],depth+1);// Traverse index Child nodes under nodes , The depth of the child node is the depth of the parent node +1; 
		// Recursive ; 
	} 
} 

int main( ){
	scanf("%d%lf%lf",&n,&p,&r);// Yes n Nodes , The price of the supplier is p, Every time you pass a dealer, the price rises r%;
	r/=100;
	for(int i=0;i<n;i++){//si The subscript is i The supplier number of the node , That is, the number of its parent node ; 
		scanf("%d",&father);// node i The subscript of the parent node of ;
		if(father!=-1){
			node[father].push_back(i);
		}else {//==-1 There is no parent node , That means the root node ; 
			root=i; 
		} 
	}
	DFS(root,0);// The depth of the root node is 0;
	printf("%.2f %d",p*pow(1+r,maxdepth),num);// One more level of depth will increase the price by percent r; 
	return 0;
}