【1079】Total Sales of Supply Chain (25 分)
1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805388447170560
给出一棵树，求出叶子结点“带权路径”之和，这里不是以前那种带权，叶子结点真正的权值由该结点的深度决定（幂次方）——根结点处货物的价格为P，叶子结点的括号内数字表示货物数。
看懂题目的输入，每行开头为当前结点i的叶子结点个数，若该首数字非0，则该行后面的数字都为i结点的叶子结点数组下标（也就是题目直接给出结点的编号，且结点的编号一定是0、1、…N-1，N为结点个数——不需要newNode函数，因为题目中给定的编号可以直接作为Node数组的下标使用）；而若该首数字为0，则该行后面的数字为叶结点的权值。
2.思路
DFS就对了，注意这题根结点的深度应设为0。
void DFS(int index,int depth){ if(Node[index].child.size()==0){//到达叶结点 ans+=Node[index].data*pow(1+r,depth); return; } for(int i=0;i<Node[index].child.size();i++){ DFS(Node[index].child[i],depth+1); } }
3.完整代码
#include<vector> #include<algorithm> #include<iostream> #include<stdlib.h> #include<stdio.h> #include<cmath> using namespace std; const int maxn=100010; double ans=0,rate; struct node{ double data; vector<int> child; }Node[maxn]; void DFS(int index,int depth){ if(Node[index].child.size()==0){ ans+=Node[index].data*pow(1+rate,depth); return; } for(int i=0;i<Node[index].child.size();i++){ DFS(Node[index].child[i],depth+1);//递归访问子结点 } } int main(){ int n; int num; double price; scanf("%d%lf%lf",&n,&price,&rate); rate/=100; for(int i=0;i<n;i++){ scanf("%d",&num); if(num==0){ scanf("%lf",&Node[i].data); }else{ for(int j=0;j<num;j++){ //scanf("%d",&Node[i].child[j]); int child; scanf("%d",&child); Node[i].child.push_back(child); } } } DFS(0,0); printf("%.1f\n",price*ans); system("pause"); }
4.注意
（1）一开始OJ提示答案错误，后来发现是定义了全局变量rate后，还在main函数里面重复定义了rate局部变量。
（2）注意scanf("%d",&Node[i].child[j])这样写不对。
（3）题目给定的rate是百分数，因此要除以100，如样例的rate=1.00指1%。
【1090】Highest Price in Supply Chain (25 分)
1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805376476626944
2.思路
和上一题类似，区别是这个要求所有叶结点中的最高价格（每层的货物价格会在父结点的价格上增加r%）和这个价格的叶结点总个数，也即【1090】的叶子结点的“初始”点权值是相同的，即只要计算深度最深的结点。
由于不用考虑结点的点权，可以不用设结构体结点了，而直接用vector<int>child[MAXV]替代，每个child[i]都是一个vector，存放各个结点的所有子结点下标。
3.完整代码
#include<vector> #include<algorithm> #include<iostream> #include<stdlib.h> #include<stdio.h> #include<cmath> using namespace std; const int maxn=100010; int num=0;//最大深度的结点个数 vector<int>child[maxn]; int maxdepth=0; double ans; double rate,price; void DFS(int index,int depth){ if(child[index].size()==0){ if(depth>maxdepth){//递归边界：到达叶结点 maxdepth=depth; ans=price*pow(1+rate,maxdepth); //printf("%lf\n",price); num=1;//重置最大深度的结点个数为1 }else if(depth==maxdepth){ num++; ans=price*pow(1+rate,maxdepth);//别漏了这句 } return; } for(int i=0;i<child[index].size();i++){//注意判断的下标不是i DFS(child[index][i],depth+1); } } int main(){ int n,father,root; scanf("%d%lf%lf",&n,&price,&rate); rate/=100; for(int i=0;i<n;i++){ scanf("%d",&father); if(father!=-1) //child[father][i]=i; child[father].push_back(i);//i是father的子结点 else root=i; } DFS(root,0); printf("%.2f %d\n",ans,num); system("pause"); }
4.注意
（1）根结点显然没有父结点，所以输入的第二行中遇到-1时的i即为root。
（2）题目给定的rate是百分数，因此要除以100，如样例的rate=1.00指1%。
