結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー Brandon Li
提出日時 2025-07-25 13:06:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 233 ms / 3,000 ms
コード長 1,790 bytes
コンパイル時間 2,462 ms
コンパイル使用メモリ 208,932 KB
実行使用メモリ 62,088 KB
最終ジャッジ日時 2025-07-25 13:06:16
合計ジャッジ時間 7,716 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#define dbgn(...) 0
#endif

const int MAXN = 200005;

vector<int> adj[MAXN];
int d[MAXN];
ll ans = 0;
int N;

void dfs1(int u, int p) {
    d[u] = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u);
        d[u] = max(d[u], 1 + d[v]);
    }
}

void dfs2(int u, int p, int up_val) {
    vector<int> branches;
    if (p != 0) {
        branches.push_back(up_val);
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        branches.push_back(1 + d[v]);
    }

    sort(branches.begin(), branches.end());
    for (size_t i = 0; i < branches.size(); i++) {
        ll len = branches[i];
        ll count = branches.size() - i;
        ans = max(ans, (ll)1 + len * count);
    }

    vector<pair<int, int>> c_paths;
    for (int v : adj[u]) {
        if (v == p) continue;
        c_paths.push_back({1 + d[v], v});
    }
    sort(c_paths.rbegin(), c_paths.rend());

    for (int v : adj[u]) {
        if (v == p) continue;
        
        int up_alt = up_val;
        if (!c_paths.empty()) {
            if (c_paths[0].second == v) { 
                if (c_paths.size() > 1) {
                    up_alt = max(up_alt, c_paths[1].first);
                }
            } else {
                up_alt = max(up_alt, c_paths[0].first);
            }
        }
        int next_up = 1 + up_alt;
        dfs2(v, u, next_up);
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ans = 1;
    dfs1(1, 0);
    dfs2(1, 0, 0);
    cout << ans << '\n';
    return 0;
}
0