結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー iastm
提出日時 2025-07-19 20:42:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 301 ms / 3,000 ms
コード長 1,606 bytes
コンパイル時間 1,516 ms
コンパイル使用メモリ 115,560 KB
実行使用メモリ 55,372 KB
最終ジャッジ日時 2025-07-19 20:42:32
合計ジャッジ時間 7,243 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int main() {
    int N;
    std::cin >> N;
    std::vector<std::vector<int>> graph(N);
    std::vector<int> dist(N, 0);
    while (--N) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
    }
    {
        auto dist_dfs = [&](const auto &dist_dfs, const int &u, const int &parent) -> void {
            for (int &v : graph[u]) {
                if (v == parent) continue;
                dist_dfs(dist_dfs, v, u);
                dist[u] = std::max(dist[u], dist[v] + 1);
            }
        };
        dist_dfs(dist_dfs, 0, -1);
    }

    auto solve = [&](const auto &solve, const int &u, const int &d_parent, const int &parent) -> int {
        std::vector<std::pair<int, int>> branches{{0, -1}};
        for (int &v : graph[u]) {
            if (v == parent) branches.emplace_back(d_parent + 1, v);
            else branches.emplace_back(dist[v] + 1, v);
        }
        std::sort(branches.rbegin(), branches.rend());
        int result = 0;
        for (int i = 0; i < branches.size(); i++) {
            result = std::max(result, (i + 1) * branches[i].first + 1);
        }
        for (int &v : graph[u]) {
            if (v == parent) continue;
            if (branches[0].second == v) result = std::max(result, solve(solve, v, branches[1].first, u));
            else result = std::max(result, solve(solve, v, branches[0].first, u));
        }
        return result;
    };
    std::cout << solve(solve, 0, 0, -1) << std::endl;
}
0