PAT tree DP (memory search) class a, 1079, 1090, 1106

树状dp：Used for any node in the tree to the root node distance

模板：

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}

原题链接：

1079 供应链总销售额

1090 供应链最高价格

1106 供应链最低价格

题目：

供应链总销售额

Supply chain is made up of retailers,Dealers and suppliers of sales network,Everyone involved in moving products from suppliers to customers.

The whole sales network can be viewed as a tree structure,From the roots of suppliers,Each person to buy goods from vendors at the next higher level after,Assume that buying price for P,Will bid higher than that of in r% The price down to sell.

Only the retailer（即叶节点）Can directly to sell the products to the customer.

现在,Given the whole sales network,Would you please calculate all retailers total sales.

输入格式
The first line contains three number,N Said the supply chain to the total number of members（All the members of the Numbers from 0 到 N−1,The roots of supplier Numbers for 0）,P Said the roots of suppliers of each product's selling price,r,Premium percentage.

接下来 N 行,Each row contains a member information,格式如下：

Ki ID[1] ID[2] … ID[Ki]
其中第 i 行,Ki Said from the supplier i A member of the direct purchase number,接下来 Ki An integer is the serial number of members of each stock.

如果某一行的 Kj 为 0,Said this is retailers,Then later only will follow a number,Said to sell to customer product total number.

输出格式
Output total sales,保留一位小数.

数据范围
1≤N≤105,
0<P≤1000,
0<r≤50
Each retailer in the hands of the product is not more than 100 件.
Ultimate answer to ensure that no more than 1010.

输入样例：
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
输出样例：
42.4

我的解法：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
double R, P;
int p[N], f[N], cnt[N];

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}
int main(){
    int n;
    cin >> n >> P >> R;
    memset(f, -1, sizeof f);
    memset(p, -1, sizeof p);
    for(int i = 0; i < n; i ++ ){
        int k;
        cin >> k;
        for(int j = 0; j < k; j ++ ){
            int son;
            cin >> son;
            p[son] = i;
        }
        
        if(k == 0) cin >> cnt[i];
    }
    
    double res = 0;
    for(int i = 0; i < n; i ++ ){
        if(cnt[i]){
            res += cnt[i] * P * pow(1 + R/100, dfs(i));
        }
    }
    
    printf("%.1lf", res);
    return 0;
}

供应链最高价格

Supply chain is made up of retailers,Dealers and suppliers of sales network,Everyone involved in moving products from suppliers to customers.

The whole sales network can be viewed as a tree structure,From the roots of suppliers,Each person to buy goods from vendors at the next higher level after,Assume that buying price for P,Will bid higher than that of in r% The price down to sell.

Only the retailer（即叶节点）Can directly to sell the products to the customer.

现在,Given the whole sales network,Would you please calculate retailers can achieve the highest selling price.

输入格式
The first line contains three number,N Said the supply chain to the total number of members（All the members of the Numbers for 0 到 N−1);P Said the roots of supplier product sales price;r,Said percentage premium.

第二行包含 N 个数字,第 i 个数字 Si 是编号为 i The serial number of the members of the superior supplier.The roots of suppliers Sroot 为 -1.

输出格式
Output retailers can achieve the highest selling price,保留两位小数,The number of retailers and can achieve the highest selling price.

数据范围
1≤N≤105,
0<P≤1000,
0<r≤50,
Ultimate answer to ensure that no more than 1010.

输入样例：
9 1.80 1.00
1 5 4 4 -1 4 5 3 6
输出样例：
1.85 2

我的解法：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
double P, R;
int p[N], f[N];

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}

int main(){
    cin >> n >> P >> R;
    
    memset(p, -1, sizeof p);
    for(int i = 0; i < n; i ++ ){
        int father;
        cin >> father;
        p[i] = father;
    }
    
    memset(f, -1, sizeof f);
    
    int cnt = 0, res = 0;
    for(int i = 0; i < n; i ++ ){
        if(dfs(i) > res){
            res = dfs(i);
            cnt = 1;
        }
        else if(dfs(i) == res) cnt ++;
    }
    
    printf("%.2lf %d", P * pow(1 + R / 100, res), cnt);
    return 0;
}

供应链最低价格

Supply chain is made up of retailers,Dealers and suppliers of sales network,Everyone involved in moving products from suppliers to customers.

The whole sales network can be viewed as a tree structure,From the roots of suppliers,Each person to buy goods from vendors at the next higher level after,Assume that buying price for P,Will bid higher than that of in r% The price down to sell.

Only the retailer（即叶节点）Can directly to sell the products to the customer.

现在,Given the whole sales network,Would you please calculate retailers can achieve the lowest selling price.

输入格式
The first line contains three number,N Said the supply chain to the total number of members（All the members of the Numbers from 0 到 N−1,The roots of supplier Numbers for 0）,P Said the roots of supplier product selling price,r,Premium percentage.

接下来 N 行,Each row contains a member information,格式如下：

Ki ID[1] ID[2] … ID[Ki]
其中第 i 行,Ki Said from the supplier i A member of the direct purchase number,接下来 Ki An integer is the serial number of members of each stock.

如果 Kj 为 0 则表示第 j Members of the team is a retailer.

输出格式
Output retailers can achieve the lowest selling price,保留四位小数,The number of retailers and can reach the lowest selling price.

数据范围
1≤N≤105,
0<P≤1000,
0<r≤50,
Ultimate answer to ensure that no more than 1010
输入样例：
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0
输出样例：
1.8362 2

我的解法：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e9;
int n;
double P, R;
int p[N], f[N];
bool is_leaf[N];

int dfs(int i){
    if(f[i] != -1) return f[i];
    if(p[i] == -1) return f[i] = 0;
    return f[i] = dfs(p[i]) + 1;
}

int main(){
    cin.tie();
    cin >> n >> P >> R;
    memset(p, -1, sizeof p);

    for(int i = 0; i < n; i ++ ){
        int k;
        cin >> k;
        for(int j = 0; j < k; j ++ ){
            int son;
            cin >> son;
            p[son] = i;
        }
        if(k == 0) is_leaf[i] = true;
    }
    

    memset(f, -1, sizeof f);
    int res = INF, cnt = 0;
    for(int i = 0; i < n; i ++ ){
        if(is_leaf[i]){
            if(dfs(i) < res){
                res = dfs(i);
                cnt = 1;
            }
            else if(dfs(i) == res) cnt ++ ;
        }
    }
    
    printf("%.4lf %d", P * pow(1 + R / 100, res), cnt);
    return 0;
}