【每日一题】Problem 120F. Spiders

原题

解决思路

通过给定的数据，将其构建称树，取其中最大的深度进行拼接，最后得到最终结果

如何获取最大的深度

以每个节点作为 root 构建树，然后取其中最大的深度

#include <bits/stdc++.h>

/**
 * @param vec
 * @param cur   当前节点
 * @param last  上一个访问的节点
 * @param level 当前节点所在层级
 * @param depth 以最初的 cur 节点作为 root 节点的树的深度
 */
void dfs(std::vector<std::vector<int>> &vec, int cur, int last, int level, int &depth) {
    for (int i = 0; i < vec[cur].size(); ++i) {
        if (vec[cur][i] == last) continue;
        dfs(vec, vec[cur][i], cur, level + 1, depth);
    }
    depth = std::max(depth, level);
}

int main() {
    // 使用 freopen 更改输入输出流
    std::freopen("input.txt", "r", stdin);
    std::freopen("output.txt", "w", stdout);
    int n; std::cin >> n;
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int p; std::cin >> p;
        std::vector<std::vector<int>> vec(p+1, std::vector<int>());
        int x, y;
        for (int j = 0; j < p - 1; ++j) {
            std::cin >> x >> y;
            vec[x].push_back(y);
            vec[y].push_back(x);
        }
        // 以每个 cur 作为 root，计算出所有可能的树中最大的深度
        int depth = 0;
        for (int cur = 1; cur <= p; ++cur)
            dfs(vec, cur, 0, 1, depth);
        res += depth;
    }

    res -= n; // equals res = res - (n-1) - 1
    std::cout << res << std::endl;
    return 0;
}