首页 > 代码库 > ZJU PAT 1090
ZJU PAT 1090
依题意构造树并遍历,找出最大深度并统计
#include <iostream>#include <vector>using namespace std;struct Node { vector<int> children; int depth;};Node nodes[100005];int maxDepth = 0;int total = 1;void travel(int n, int d) { Node& node = nodes[n]; node.depth = d; int size = node.children.size(); if (size > 0) { ++d; if (d > maxDepth) { maxDepth = d; total = size; } else if (d == maxDepth) { total += size; } for (int i = 0; i != size; ++i) { travel(node.children[i], d); } }}int main() { int n; double price, rate; scanf("%d %lf %lf", &n, &price, &rate); rate = rate / 100.0 + 1.0; int root = -1; for (int i = 0; i != n; ++i) { int m; scanf("%d", &m); if (m == -1) { root = i; } else { nodes[m].children.push_back(i); } nodes[i].depth = 0; } travel(root, 0); price *= pow(rate, maxDepth); printf("%.2lf %d\n", price, total); return 0;}
ZJU PAT 1090
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。