結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー amesyu
提出日時 2026-03-05 17:55:56
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 158 ms / 3,000 ms
コード長 3,078 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,565 ms
コンパイル使用メモリ 204,152 KB
実行使用メモリ 26,856 KB
最終ジャッジ日時 2026-03-05 17:56:04
合計ジャッジ時間 5,274 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// Generated By Gemini 3.1 Pro for test

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // BFSで開始点からの距離を計算し、最も遠い頂点を返すラムダ式
    auto bfs = [&](int start, vector<int>& dist) {
        dist.assign(N + 1, -1);
        queue<int> q;
        q.push(start);
        dist[start] = 0;
        int farthest_node = start;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                    farthest_node = v;
                }
            }
        }
        return farthest_node;
    };

    vector<int> dist_from_any, dist_X, dist_Y;
    
    // 1. 直径の端点 X, Y を求める
    int X = bfs(1, dist_from_any);
    int Y = bfs(X, dist_X);
    bfs(Y, dist_Y);
    
    int diameter = dist_X[Y]; // 木の直径

    // 2. 通常の木DP (Xを根とする)
    vector<int> height(N + 1, 0);
    vector<int> parent(N + 1, 0);
    
    // ボトムアップで部分木の深さを計算
    auto dfs = [&](auto& self, int u, int p) -> void {
        parent[u] = p;
        for (int v : adj[u]) {
            if (v == p) continue;
            self(self, v, u);
            height[u] = max(height[u], height[v] + 1);
        }
    };
    dfs(dfs, X, 0);

    long long ans = 1;

    // 3. 各頂点を中心としたウニ木の最大サイズを計算
    for (int i = 1; i <= N; ++i) {
        vector<long long> L; // 各方向への最長パス長
        
        for (int v : adj[i]) {
            if (v == parent[i]) {
                // 親方向への辺
                // 頂点 i が直径 X-Y のパス上にあるか判定
                if (dist_X[i] + dist_Y[i] == diameter) {
                    // パス上にある場合、Y は部分木側にあるため、親方向の最遠点は X のみ
                    L.push_back(dist_X[i]); 
                } else {
                    // パス上にない場合、親方向の最遠点は X か Y の遠い方
                    L.push_back(max(dist_X[i], dist_Y[i]));
                }
            } else {
                // 子方向への辺（通常の木DPの結果）
                L.push_back(height[v] + 1);
            }
        }
        
        // 降順にソートして貪欲に計算
        sort(L.rbegin(), L.rend());
        
        for (int k_idx = 0; k_idx < L.size(); ++k_idx) {
            long long branches = k_idx + 1;
            long long depth = L[k_idx];
            ans = max(ans, branches * depth + 1);
        }
    }

    cout << ans << "\n";
    return 0;
}
0