AcWing 1596. 供应链最低价格
原题链接
简单
作者:
xxxxuu
,
2021-08-22 17:29:59
,
所有人可见
,
阅读 257
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=100010;
int n;
double p,r;
int cnt[N]; //记录当前层叶子结点的数量
int min_depth=N; //记录叶子结点所在的最低层数
vector<int> tree[N]; //模拟树
void dfs(int root,int depth){
if(tree[root].size()==0){
cnt[depth]++;
min_depth=min(depth,min_depth);
}
for(int i=0;i<tree[root].size();i++){
dfs(tree[root][i],depth+1);
}
}
int main(){
cin>>n>>p>>r;
r/=100.0;
for(int i=0;i<n;i++){
int k;
cin>>k;
while(k--){
int child;
cin>>child;
tree[i].push_back(child);
}
}
dfs(0,0);
printf("%0.4f %d\n",p*pow(1+r,min_depth),cnt[min_depth]);
return 0;
}