个人练习-PAT甲级-1079 Total Sales of Supply Chain

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805388447170560

树的DFS，应该不算难。但由于本人的陋习，这种涉及叶子到根的DFS都喜欢从下往上搜（即从叶子搜索到根）（感觉是为了节省空间），最后一个点超时了。看了柳神的解法也是要至少双层数组，强迫症犯了，没有照抄，把自己的自底向上DFS剪了减枝，然后就过了（耶~）

读入数据，parent[]数组保存每个节点的父亲，lvl[]保存每个节点的深度（层数）。根的深度为0

    int N;double P, r;scanf("%d %lf %lf", &N, &P, &r);vector<int> parent(N, -1);vector<Retailer> rtl;vector<int> lvl(N, -1);lvl[0] = 0;

rtl[]数组存叶子节点的编号和销售量，也就是retailers

class Retailer {
    
public:int id;int amt;
};

读入数据，如果是叶子节点（K==0），就放入rtl[]数组中；如果不是，就记录将它的孩子的parent值置为它，记录每个节点的父亲。

    for (int i = 0; i < N; i++) {
    int K;scanf("%d", &K);if (K == 0) {
    Retailer tmp;scanf("%d", &tmp.amt);tmp.id = i;rtl.push_back(tmp);continue;}for (int j = 0; j < K; j++) {
    int kid;scanf("%d", &kid);parent[kid] = i;}}

对每一个叶子节点，找它的父亲节点，若父亲节点的层数已经记录了，就直接用其层数+1计算销售额；否则先获取父亲节点的层数。

    double ret = 0.0;for (int i = 0; i < rtl.size(); i++) {
    double sale = rtl[i].amt * P;int nxt = parent[rtl[i].id];while (nxt != -1) {
    if (lvl[nxt] >= 0) {
    sale *= pow((1 + r / 100.0), lvl[nxt] + 1);break;}else    getLvl(nxt, parent, lvl); }ret += sale;}

获取层数函数，如果父亲节点层数已知，就置为父亲层数+1；否则继续向上直到根。（根的层数已初始置为0）

int getLvl(int nxt, vector<int>& parent, vector<int>& lvl) {
    if (lvl[parent[nxt]] >= 0) lvl[nxt] = lvl[parent[nxt]] + 1;else lvl[nxt] = getLvl(parent[nxt], parent, lvl) + 1;return lvl[nxt];
}

因为有了lvl[]记录层数，从叶子节点出发，就不需要每次都追溯到根了，节省了时间，测试点6就可以过了。

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;class Retailer {
    
public:int id;int amt;
};int getLvl(int nxt, vector<int>& parent, vector<int>& lvl) {
    if (lvl[parent[nxt]] >= 0)lvl[nxt] = lvl[parent[nxt]] + 1;elselvl[nxt] = getLvl(parent[nxt], parent, lvl) + 1;return lvl[nxt];
}int main() {
    int N;double P, r;scanf("%d %lf %lf", &N, &P, &r);vector<int> parent(N, -1);vector<Retailer> rtl;vector<int> lvl(N, -1);lvl[0] = 0;for (int i = 0; i < N; i++) {
    int K;scanf("%d", &K);if (K == 0) {
    Retailer tmp;scanf("%d", &tmp.amt);tmp.id = i;rtl.push_back(tmp);continue;}for (int j = 0; j < K; j++) {
    int kid;scanf("%d", &kid);parent[kid] = i;}}double ret = 0.0;for (int i = 0; i < rtl.size(); i++) {
    double sale = rtl[i].amt * P;int nxt = parent[rtl[i].id];while (nxt != -1) {
    if (lvl[nxt] >= 0) {
    sale *= pow((1 + r / 100.0), lvl[nxt] + 1);break;}else    getLvl(nxt, parent, lvl); }ret += sale;}printf("%.1f", ret);return 0;
}