领接表 + DFS

1.用邻接表存储树
2.DFS递归到根节点计算出总金额

C++ 代码

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

const int MAX_N = 100010;

int edge[MAX_N], nextEdge[MAX_N];
int vertex[MAX_N],idx;
int products[MAX_N];
int n;
double p, r;

void AddEdge(int v, int w) {
    vertex[idx] = w;
    nextEdge[idx] = edge[v];
    edge[v] = idx++;
}

double total;
void DFS(int v, double p) {
    if (products[v] > 0) {
        total += p * products[v];
        return;
    }
    for (int i = edge[v]; i != -1; i = nextEdge[i]) {
        int w = vertex[i]; 
        DFS(w, p * (100 + r) / 100);
    }
}

int main() {
    cin >> n >> p >> r;
    memset(edge, -1, sizeof edge);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        if (k > 0) {
            for (int j = 0; j < k; j++) {
                int w;
                cin >> w;
                AddEdge(i, w);
            }
        }
        else {
            cin >> products[i];
        }
    }
    DFS(0, p);
    printf("%.1f\n", total);
    return 0;
}