結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
|
提出日時 | 2025-07-18 22:05:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 3,000 ms |
コード長 | 1,674 bytes |
コンパイル時間 | 4,573 ms |
コンパイル使用メモリ | 256,544 KB |
実行使用メモリ | 89,940 KB |
最終ジャッジ日時 | 2025-07-18 22:05:40 |
合計ジャッジ時間 | 7,227 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template <class T> bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template <class T> bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; void solve() { int n; cin >> n; vector<vector<int>> g(n); rep(i, 0, n - 1) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } vector<int> childs(n); { auto dfs = [&](auto self, int nw, int pr) -> void { int res = 0; for (int nx : g[nw]) { if (nx == pr) continue; self(self, nx, nw); chmax(res, childs[nx] + 1); } childs[nw] = res; }; dfs(dfs, 0, -1); } ll ans = 0; { auto dfs = [&](auto self, int nw, int pr, int p_val) -> void { vector<int> v = {p_val}; for (int nx : g[nw]) { if (nx == pr) continue; v.push_back(childs[nx] + 1); } auto sv = v; rep(i, 0, v.size() - 1) chmax(sv[i + 1], sv[i]); auto rsv = v; for (int i = v.size() - 1; i > 0; i--) chmax(rsv[i - 1], rsv[i]); rsv.push_back(0); int it = 0; for (int nx : g[nw]) { if (nx == pr) continue; self(self, nx, nw, max(sv[it], rsv[it + 2]) + 1); it++; } sort(v.begin(), v.end()); reverse(v.begin(), v.end()); rep(i, 0, v.size()) { chmax(ans, (i + 1) * v[i] + 1); } }; dfs(dfs, 0, -1, 0); } cout << ans << "\n"; } int main() { int t = 1; // cin >> t; while (t--) solve(); }