1、题意
求叶⼦结点出能获得的最低价格(最小深度)以及能提供最低价格的叶⼦结点数
2、判断题目为树的dfs
3、设计dfs
>1 因为给出下标编号,所以选择静态存储 vector<int> tree[maxn];
>2 需要从dfs中get的:叶子数、叶子的最低深度,深度更新时叶子数要置零
>3 每次的变量,处理的结点index + 深度
>4 采用循环写法
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
const int maxn=100100;
int n;
double p,r;
vector<int> tree[maxn];
int dp=maxn;//ans
int count;
void dfs(int index,int depth){
if(tree[index].size()==0){
if(depth<dp){
dp=depth;count=1;
}else if(depth==dp){
count++;
}
return;
}
for(int i=0;i<tree[index].size();i++){
dfs(tree[index][i],depth+1);
}
}
int main(){
scanf("%d %lf %lf",&n,&p,&r);
r=r*0.01;
for(int i=0;i<n;i++){
int d,id;
scanf("%d",&d);
for(int j=0;j<d;j++){
scanf("%d",&id);
tree[i].push_back(id);
}
}
dfs(0,0);
printf("%.4f %d",p*pow(1+r,dp),count);
return 0;
}