結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }