結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = modint998244353;
using ll = long long;
#define fix(x) fixed << setprecision(x)
#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}
constexpr ll INFLL = (1LL << 62), MOD = 998244353;
constexpr int INF = (1 << 30);

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    rep(i,n-1){
        int u,v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<vector<int>> dp(n);
    auto dfs1 = [&](auto self, int now, int par) -> int {
        int res = 0;
        for(int x:g[now]){
            if(x==par) continue;
            int val = self(self, x, now);
            dp[now].emplace_back(val);
            chmax(res, val);
        }
        return res+1;
    };
    int k = dfs1(dfs1,0,-1);
    auto dfs2 = [&](auto self, int now, int par, int z) -> void {
        int cnt = 0, m = dp[now].size();
        vector<int> r(m,0);
        for(int i=m-1;i>=1;--i) r[i-1] = max(dp[now][i], r[i]);
        int l = 0;
        for(int x:g[now]){
            if(x==par) continue;
            int p = max(z, max(l, r[cnt])) + 1;
            self(self, x, now, p);
            dp[x].emplace_back(p);
            chmax(l, dp[now][cnt++]);
        }
    };
    dfs2(dfs2,0,-1,0);
    int ans = 1;
    rep(i,n){
        sort(all(dp[i]));
        int m = dp[i].size();
        rep(j,m) chmax(ans, (m-j)*dp[i][j]+1);
    }
    cout << ans << '\n';
    return 0;
}
0