結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー V_Melville
提出日時 2025-07-18 22:58:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 244 ms / 3,000 ms
コード長 3,027 bytes
コンパイル時間 2,879 ms
コンパイル使用メモリ 285,096 KB
実行使用メモリ 34,692 KB
最終ジャッジ日時 2025-07-18 22:58:41
合計ジャッジ時間 7,223 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

const int MAXN = 200005;

vector<int> to[MAXN];
int dv[MAXN], uv[MAXN];
int bdr[MAXN], sbr[MAXN], cbr[MAXN];
int pa[MAXN];
long long ans = 0;

void dfs1(int u, int p) {
    pa[u] = p;
    dv[u] = 0;
    bdr[u] = -1;
    sbr[u] = -1;
    cbr[u] = 0;

    for (int v : to[u]) {
        if (v == p) continue;
        dfs1(v, u);
        int child_down = dv[v];
        if (child_down > bdr[u]) {
            sbr[u] = bdr[u];
            bdr[u] = child_down;
            cbr[u] = 1;
        } else if (child_down == bdr[u]) {
            cbr[u]++;
        } else if (child_down > sbr[u]) {
            sbr[u] = child_down;
        }
        dv[u] = max(dv[u], child_down + 1);
    }
}

void dfs2(int u, int p) {
    if (p != -1) {
        int other_max;
        if (dv[u] == bdr[p]) {
            if (cbr[p] > 1) {
                other_max = bdr[p];
            } else {
                other_max = sbr[p];
            }
        } else {
            other_max = bdr[p];
        }
        if (other_max == -1) {
            uv[u] = uv[p] + 1;
        } else {
            uv[u] = max(uv[p] + 1, other_max + 2);
        }
    }

    for (int v : to[u]) {
        if (v == p) continue;
        dfs2(v, u);
    }
}

int main() {
    int n;
    cin >> n;
    
    rep(i, n-1) {
        int u, v;
        cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }

    dfs1(1, -1);
    uv[1] = 0;
    for (int child : to[1]) {
        dfs2(child, 1);
    }

    ans = 0;
    for (int u = 1; u <= n; u++) {
        vector<int> branches;
        if (pa[u] != -1) {
            int p = pa[u];
            int other_max;
            if (dv[u] == bdr[p]) {
                if (cbr[p] > 1) {
                    other_max = bdr[p];
                } else {
                    other_max = sbr[p];
                }
            } else {
                other_max = bdr[p];
            }
            int depth_pa;
            if (other_max == -1) {
                depth_pa = uv[p];
            } else {
                depth_pa = max(uv[p], other_max + 1);
            }
            branches.push_back(depth_pa);
        }
        for (int v : to[u]) {
            if (v == pa[u]) continue;
            branches.push_back(dv[v]);
        }

        if (branches.empty()) {
            ans = max(ans, 1ll);
            continue;
        }

        sort(branches.begin(), branches.end(), greater<int>());
        int m = branches.size();
        long long now = 0;
        int i = 0;
        while (i < m) {
            int v = branches[i];
            auto it = upper_bound(branches.begin(), branches.end(), v, greater<int>());
            int cnt = it - branches.begin();
            long long t = 1 + (long long)cnt * (v + 1);
            now = max(now, t);
            while (i < m && branches[i] == v) {
                i++;
            }
        }
        ans = max(ans, now);
    }

    cout << ans << '\n';

    return 0;
}
0