【1090】Highest Price in Supply Chain (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//key:用DFS遍历所有叶结点 求最高价格，注意pow使用
const  int maxn=100010;
vector<int> child[maxn];  //存放树
double p,r; 
//maxDepth为最大深度，num为最大深度的叶子结点个数
int n,maxDepth=0,num=0;
void DFS(int index,int depth){
  if(child[index].size() == 0) {  //到达叶子结点
    if(depth > maxDepth){  //深度比最大深度大
      maxDepth=depth;  //跟新最大深度
      num=1;         //重置最大深度的叶子结点个数为1
    }else if(depth == maxDepth) {  //深度等于最大深度
      num++;  //最大深度的叶结点个数加1
    }
    return ;//注意这个return
  }
  for(int i=0;i<child[index].size();i++){
    DFS(child[index][i],depth+1);  //递归访问结点index的子结点
  }
}
int main(){   
  int father,root;
  scanf("%d%lf%lf",&n,&p,&r);
  r/=100; //将百分数 除以100
  for(int i=0;i<n;i++){
    scanf("%d",&father);
    if(father != -1){
      child[father].push_back(i); //i是father的子结点
    }else{
      root =i; //根结点为root
    }
  }
  DFS(root,0);  //DFS入口
  printf("%.2f %d\n",p*pow(1+r,maxDepth),num);  //输出结果
  system("pause");
    return 0;   
}