树的层序遍历
// // main.cpp // PATA1079 // // Created by Phoenix on 2018/2/18. // Copyright © 2018年 Phoenix. All rights reserved. // #include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; const int maxn = 100010; struct Node { int level; int num; vector<int> v; }node[maxn]; double p, r; double ans = 0; void levelorder() { queue<int> q; q.push(0); int lastnode = 0, newlastnode = -1; double price = p; while(!q.empty()) { int top = q.front(); q.pop(); if(node[top].num > 0) { //printf("%.1f %d\n", price, node[top].num); ans += node[top].num * price; } for(int i = 0; i < node[top].v.size(); i++) { q.push(node[top].v[i]); newlastnode = node[top].v[i]; } if(top == lastnode) { price *= (1 + r / 100); lastnode = newlastnode; } } } int main(int argc, const char * argv[]) { int n; scanf("%d %lf %lf", &n, &p, &r); for(int i = 0; i < n; i++) { int k; scanf("%d", &k); if(k == 0) { int amount; scanf("%d", &amount); node[i].num = amount; } else { node[i].num = 0; for(int j = 0; j < k; j++) { int child; scanf("%d", &child); node[i].v.push_back(child); } } } levelorder(); printf("%.1f\n", ans); return 0; }