結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
![]() |
提出日時 | 2025-07-18 22:41:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 285 ms / 3,000 ms |
コード長 | 2,305 bytes |
コンパイル時間 | 3,730 ms |
コンパイル使用メモリ | 291,780 KB |
実行使用メモリ | 62,604 KB |
最終ジャッジ日時 | 2025-07-18 22:41:24 |
合計ジャッジ時間 | 7,990 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using a2 = array<ll, 2>; using a3 = array<ll, 3>; template <typename A> void chmin(A &l, const A &r) { if (r < l) l = r; } template <typename A> void chmax(A &l, const A &r) { if (l < r) l = r; } ll mod = 998244353; int main() { ios::sync_with_stdio(false); cin.tie(0); ll n; cin >> n; vector<vector<ll>> g(n); for (int i = 0; i < n - 1; i++) { ll u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } vector<vector<ll>> dp(n); vector<vector<ll>> dp_l(n); vector<vector<ll>> dp_r(n); for (int i = 0; i < n; i++) { dp[i].assign(g[i].size(), 0); dp_l[i].assign(g[i].size() + 1, 0); dp_r[i].assign(g[i].size() + 1, 0); } auto dfs = [&](auto self, int now, int par) -> ll { ll mx = 0; for (int i = 0; i < g[now].size(); i++) { auto x = g[now][i]; if (x == par) continue; dp[now][i] = self(self, x, now); chmax(mx, dp[now][i]); } mx++; return mx; }; auto dfs2 = [&](auto self, int now, int par, int idx) -> void { if (par != -1) { ll paridx = find(g[now].begin(), g[now].end(), par) - g[now].begin(); dp[now][paridx] = max(dp_l[par][idx], dp_r[par][idx + 1]) + 1; } for (int i = 0; i < g[now].size(); i++) { dp_l[now][i + 1] = max(dp_l[now][i], dp[now][i]); } for (int i = g[now].size() - 1; i >= 0; i--) { dp_r[now][i] = max(dp_r[now][i + 1], dp[now][i]); } for (int i = 0; i < g[now].size(); i++) { auto x = g[now][i]; if (x == par) continue; self(self, x, now, i); } }; dfs(dfs, 0, -1); dfs2(dfs2, 0, -1, -1); ll ans = 1; for (int i = 0; i < n; i++) { vector<ll> v; for (int j = 0; j < g[i].size(); j++) { v.push_back(dp[i][j]); } sort(v.rbegin(), v.rend()); while (v.size()) { chmax(ans, (ll)v.size() * v.back() + 1); v.pop_back(); } } cout << ans << endl; return 0; }