結果
問題 |
No.1928 Make a Binary Tree
|
ユーザー |
|
提出日時 | 2022-05-07 01:58:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 261 ms / 3,000 ms |
コード長 | 1,547 bytes |
コンパイル時間 | 2,510 ms |
コンパイル使用メモリ | 207,440 KB |
最終ジャッジ日時 | 2025-01-29 04:22:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef _RUTHEN #include "debug.hpp" #else #define show(...) true #endif using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) template <class T> using V = vector<T>; map<int, int> mp[200005]; int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; V<V<int>> G(N); rep(i, N - 1) { int x, y; cin >> x >> y; x--, y--; G[x].push_back(y); G[y].push_back(x); } auto rec = [&](auto f, int cur, int par) -> void { for (auto &nex : G[cur]) { if (nex == par) continue; f(f, nex, cur); for (auto &[val, cnt] : mp[nex]) { if (val > 0) mp[cur][val] += cnt; } } if (mp[cur].size() == 0) { mp[cur][1] += 1; return; } auto [val, cnt] = *mp[cur].rbegin(); if (cnt >= 2) { mp[cur][val] -= 2; if (mp[cur][val] == 0) mp[cur].erase(val); mp[cur][2 * val + 1] += 1; } else { mp[cur].erase(val); int ret = val; if (mp[cur].size() > 0) { auto [val2, cnt2] = *mp[cur].rbegin(); mp[cur][val2] -= 1; if (mp[cur][val2] == 0) mp[cur].erase(val2); ret += val2; } mp[cur][ret + 1] += 1; } return; }; rec(rec, 0, -1); int ans = (*mp[0].rbegin()).first; cout << ans << '\n'; return 0; }