题目链接：点击打开链接
题目大意：一个供货链是由一张零售商和经销商和供应商组成的网络——从供应商到客户之间每个人都紧紧相连。
从一个总供应商开始，每个在链上的人从各自的供应商上以P的价格买产品并以r%的利润卖给或批给其他人。只有零售商将会直面消费者。假设除了总供应商之外每个供应链上的成员都有一个供应商，并且没有供应环。
现在给你一个供应链，你需要说出所有零售商的总销售额。
每个输入文件包含一组测试数据。对于每组输入数据，第一行包括三个正整数：N(<=10^5)，供应链的总人数(因此他们的ID被标记为从0-N-1，并且总供应商的ID是0)；P，代表总供应商的原价；r，代表每个经销商或零售商的利率。接着N行，每行根据以下格式描述一个经销商或零售商：
Ki ID[1] ID[2] … ID[Ki]
在第 i 行，Ki 为从供应商 i 进货的经销商或零售商的总数，接着为这些经销商或零售商的ID号。Kj 为 0 代表第 j 个人为一个零售商，作为替代 Kj 后给出的为 Kj 卖出的商品总数。一行内所有数字之间用空格隔开。
对于每组输入数据，输出一行我们可以预测的所有零售商的总销售额，保留一位小数。数据保证数字不会大于10^10。
解题思路：邻接表创建树。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1e5+10; int n; int cnt[maxn]; double p,r,sum; vector<int> v[maxn]; void dfs(int s,double p) { if(v[s].size()==0) { sum+=p*cnt[s]; return; } for(int i=0;i<v[s].size();i++) dfs(v[s][i],r*p); } int main() { int k,u; scanf("%d%lf%lf",&n,&p,&r); r=1+r/100; for(int i=0;i<n;i++) { scanf("%d",&k); if(k==0) scanf("%d",&cnt[i]); else while(k--) scanf("%d",&u), v[i].push_back(u); } dfs(0,p); printf("%.1f\n",sum); return 0; }
