A supply chain is a network of retailers（零售商）, distributors（經銷商）, and suppliers（供應商）-- 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 (<=10^5^), 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 S~i~ is the index of the supplier for the i-th member. S~root~ 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 10^10^.
Sample Input:
9 1.80 1.00
1 5 4 4 -1 4 5 3 6
Sample Output:1.85 2
題目大意：給出一個數組a[i] = j; 表示i的供應商是j， 當a[i]=-1的時候，表示i是最頂端的供應商。求供應鏈的最長長度，以及處于最長長度供應鏈末端零售商的人數
對給出的數據做以下處理：建立一個二維vector向量，chain[i]表示i為供應商，chain[i][j]表示j的供應商是i。chain[i].size()=0 則表示i是零售商
maxdepth記錄供應鏈的最長長度，cnt記錄處于最長供應鏈末端零售商的人數。
這一題其實就是用數組建立樹，并遍歷樹的過程。從頂端供應商root開始遍歷，直到遍歷到零售商為止（即chain[i].size()=0）; 遍歷過程中，如果發現當前的depth比maxdepth大，則更新maxd，并更新cnt=1;
若遍歷過程中發現當前depth=maxdepth則更新cnt的值；
注意點：計算最高價格的時候，要用double類型， 用float類型，會有一些測試點不能通過，應該是溢出導致
在dfs（）遍歷樹的時候，不能調用dfs(index, depth++), 應該用dfs(index, depth+1); 前者會改變同意層次循環中的depth值導致最終結果錯誤
#include<iostream> #include<vector> #include<cmath> using namespace std; int cnt=0, maxdepth=0; double ans=0.0; vector<vector<int>> chain; void dfs(int index, int depth){if(chain[index].size()==0){if(depth>maxdepth){maxdepth=depth; cnt=1;}else if(depth==maxdepth) cnt++;return;}for(int i=0; i<chain[index].size(); i++) dfs(chain[index][i], depth+1); } int main(){int n, i, root, temp;double p, r;cin>>n>>p>>r;chain.resize(n);for(i=0; i<n; i++){cin>>temp;if(temp==-1){root=i; continue;}chain[temp].push_back(i);}dfs(root, 0);printf("%.2f %d", p*pow((1.0+r/100.0), maxdepth), cnt);return 0; }
?
)
)
...)
