A supply chain is a network of retailers（零售商）, distributors（經(jīng)銷商）, and suppliers（供應(yīng)商）-- 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. Only the retailers will face the customers. 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 lowest price a customer 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 (≤10^5? ), the total number of the members in the supply chain (and hence their ID's are numbered from 0 to N?1, and the root supplier's ID is 0); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:
Ki?? ID[1] ID[2] ... ID[K?i]
where in the i-th line, K?i is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID's of these distributors or retailers. K?j being 0 means that the j-th member is a retailer. All the numbers in a line are separated by a space.

Output Specification:

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

Sample Input:

10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0

Sample Output:

1.8362 2

題目大意

供應(yīng)鏈由零銷商、經(jīng)銷商、供應(yīng)商組成，從供應(yīng)商開始，供應(yīng)鏈上的每個人在購買貨物的時候需要支付比原價格多r%的費用，供應(yīng)鏈上不存在環(huán)，本題要求求出顧客為購買貨物支付的最少費用，并且求出最低價格的供應(yīng)鏈存在的條數(shù)

分析

本題涉及樹的遍歷，可以采用深度優(yōu)先遍歷或者廣度優(yōu)先遍歷，本題采用深度優(yōu)先遍歷，在遍歷的過程中記錄節(jié)點的層數(shù)，當遇到葉子節(jié)點時，判斷當前的葉子節(jié)點是否符合題目要求，若層數(shù)level小于當前記錄的層數(shù)minlevel，則更新milevel并且設(shè)置count為1（當前符合路徑的數(shù)目），若層數(shù)level等于當前記錄的層數(shù)milevel，則說明有找到了一條符合題意的路徑，則自加1

 #include <iostream>
 #include <cmath>
 #include <vector>
 using namespace std;
 vector<vector<int> > v;
 vector<int> level;
 int count=1,minlevel=100010;
 void dfs(int u,int l){
    if(v[u].size()==0){
        level[u]=l;
        if(minlevel>l){
            count=1;
            minlevel=l;
         }else if(minlevel==l){
            count++;
         }
     }else{
        for(int w=0;w<v[u].size();w++){
            dfs(v[u][w],l+1);
         }
     }  
 }
 int main(){
    int n;
    double price,rate;
    cin>>n>>price>>rate;
    v.resize(n),level.resize(n);
    for(int i=0;i<n;i++){
        int cnt;
        cin>>cnt;
        v[i].resize(cnt);
        for(int j=0;j<cnt;j++){
            cin>>v[i][j];
         }
     }
     dfs(0,0);
     double ans=price*pow(1+rate/100.0,minlevel); 
     printf("%.4lf %d",ans,count);
    return 0;
 }