题意分析

给定一棵家谱树及一个整数 $d$，需找出每个成员第 $d$ 代后代的人数，统计后输出后代数最多的前三名（注意这里包含并列的情况）。若某人第 $d$ 代后代为 0，不计入排名。

解题思路

1. 数据读取：用 map<string, vector<string>> children 存储每个人的直接子女列表，并记录所有姓名。

2. 计算第 $d$ 代后代数：对每个成员，进行深度优先搜索（DFS）或广度优先搜索（BFS）遍历其子树，到达深度 $d$ 时统计该层节点数。

3. 结果计算：对每个姓名 name 调用 cnt = countDesc(name, d)，若 cnt > 0则记录。对结果集合 res 按“后代数”降序、“姓名”升序排序，输出前 3 名。

本题代码

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef map<string, vector<string> > MVS;

MVS children;

// 递归计算第 d 代后代数
int countDesc(const string &u, int d) {
    if (d == 0) {
        return 1;
    }
    int cnt = 0;
    vector<string> &chs = children[u];
    for (size_t i = 0; i < chs.size(); ++i) {
        cnt += countDesc(chs[i], d - 1);
    }
    return cnt;
}

// 按后代数降序，姓名升序排序
bool cmpPair(const pair<string,int> &a, const pair<string,int> &b) {
    if (a.second != b.second) {
        return a.second > b.second;
    }
    return a.first < b.first;
}

int main() {
    int T;
    if (!(cin >> T)) {
        return 0;
    }

    for (int tc = 1; tc <= T; ++tc) {
        int n, d;
        cin >> n >> d;
        children.clear();

        vector<string> names;
        string name;
        for (int i = 0; i < n; ++i) {
            cin >> name;
            names.push_back(name);
            int m;
            cin >> m;
            vector<string> list;
            for (int j = 0; j < m; ++j) {
                string c;
                cin >> c;
                list.push_back(c);
            }
            children[name] = list;
        }

        // 收集所有 count>0 的成员
        vector<pair<string,int> > res;
        for (size_t i = 0; i < names.size(); ++i) {
            int cnt = countDesc(names[i], d);
            if (cnt > 0) {
                res.push_back(make_pair(names[i], cnt));
            }
        }

        // 排序并输出
        sort(res.begin(), res.end(), cmpPair);
        printf("Tree %d:
", tc);

        int printed = 0;
        for (size_t i = 0; i < res.size(); ++i) {
            if (printed >= 3 && res[i].second != res[i - 1].second) {
                break;
            }
            cout << res[i].first << " " << res[i].second << "
";
            ++printed;
        }

        if (tc != T) {
            cout << "
";
        }
    }

    return 0;
}