首页 > 代码库 > 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