結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
|
提出日時 | 2025-07-19 13:36:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 714 ms / 3,000 ms |
コード長 | 8,551 bytes |
コンパイル時間 | 3,835 ms |
コンパイル使用メモリ | 305,744 KB |
実行使用メモリ | 220,276 KB |
最終ジャッジ日時 | 2025-07-19 13:36:53 |
合計ジャッジ時間 | 13,937 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.hpp> #else template <class T> concept Streamable = requires(ostream os, T &x) { os << x; }; template <class mint> concept is_modint = requires(mint &x) { { x.val() } -> std::convertible_to<int>; }; #define debug(...) #endif template <Streamable T> void print_one(const T &value) { cout << value; } template <is_modint T> void print_one(const T &value) { cout << value.val(); } void print() { cout << '\n'; } template <class T, class... Ts> void print(const T &a, const Ts &...b) { print_one(a); ((cout << ' ', print_one(b)), ...); cout << '\n'; } template <ranges::range Iterable> requires(!Streamable<Iterable>) void print(const Iterable &v) { for(auto it = v.begin(); it != v.end(); ++it) { if(it != v.begin()) cout << " "; print_one(*it); } cout << '\n'; } using vi = vector<int>; using vii = vector<vector<int>>; using pii = pair<int, int>; using ll = long long; using vl = vector<ll>; using vll = vector<vl>; using pll = pair<ll, ll>; #define all(v) begin(v), end(v) template <class T> void UNIQUE(T &v) { ranges::sort(v); v.erase(unique(all(v)), end(v)); } template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } // https://trap.jp/post/1224/ template <class... T> constexpr auto min(T... a) { return min(initializer_list<common_type_t<T...>>{a...}); } template <class... T> constexpr auto max(T... a) { return max(initializer_list<common_type_t<T...>>{a...}); } template <class... T> void input(T &...a) { (cin >> ... >> a); } template <class T> void input(vector<T> &a) { for(T &x : a) cin >> x; } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1_0(n, c) REP1_1(n, c) #define REP1_1(n, c) \ for(ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(n); REP_COUNTER_##c++) #define REP1(n) REP1_0(n, __COUNTER__) #define REP2(i, a) for(ll i = 0; i < (ll)(a); i++) #define REP3(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++) #define REP4(i, a, b, c) for(ll i = (ll)(a); i < (ll)(b); i += (ll)(c)) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; template <class T> constexpr T floor(T x, T y) noexcept { return x / y - ((x ^ y) < 0 and x % y); } template <class T> constexpr T ceil(T x, T y) noexcept { return x / y + ((x ^ y) >= 0 and x % y); } // yの符号に関わらず非負で定義 \bmod:texコマンド template <class T> constexpr T bmod(T x, T y) noexcept { T m = x % y; return (m < 0) ? m + (y > 0 ? y : -y) : m; } template <std::signed_integral T> constexpr int bit_width(T x) noexcept { return std::bit_width((uint64_t)x); } template <std::signed_integral T> constexpr int popcount(T x) noexcept { return std::popcount((uint64_t)x); } constexpr bool kth_bit(auto n, auto k) { return (n >> k) & 1; } #line 3 "graph/graph-template.hpp" /** * @brief Graph Template(グラフテンプレート) * @see https://ei1333.github.io/library/graph/graph-template.hpp */ template <class T = ll> struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} Edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <class T = ll> struct Graph { using cost_type = T; vector<vector<Edge<T>>> g; int es; // edge_size Graph() = default; explicit Graph(int n) : g(n), es(0) {}; int size() const { return ssize(g); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } vector<Edge<T>> &operator[](const int &k) { return g[k]; } const vector<Edge<T>> &operator[](const int &k) const { return g[k]; } void read(int m, int padding = -1, bool weighted = false, bool directed = false) { for(int i = 0; i < m; ++i) { int a, b; T c(1); cin >> a >> b; a += padding; b += padding; if(weighted) cin >> c; if(directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } }; #line 3 "tree/rerooting.hpp" /* 今の実装では0を根としたときに葉に向かう辺しか見ていない 辺の向きによってcostを変えるような場合には対応していない apply関数、idxもほしいしEdge<Cost>を引数にする? でも↑の事情からfrom,toが入れ替わっている可能性がある */ // https://atcoder.jp/contests/abc222/editorial/2749 // https://nyaannyaan.github.io/library/tree/rerooting.hpp // TreeType : Graph<Cost> // MergeFunc : Data(Data,Data) // ApplyFunc : Data(Data,int from,int to,Cost) /* using Data = ; using Cost = ; Graph<Cost> g; Data leaf = ; auto merge = [](Data a, Data b) {}; auto apply = [](Data data, int from, int to, Cost cost) {}; Rerooting<Data, decltype(g), decltype(merge), decltype(apply)> dp( g, merge, apply, leaf); */ template <class Data, class TreeType, class MergeFunc, class ApplyFunc> struct Rerooting { const TreeType &g; const MergeFunc merge; const ApplyFunc apply; const Data leaf; vector<Data> dp, memo; Rerooting(const TreeType &g, MergeFunc merge, ApplyFunc apply, Data leaf) : g(g), merge(merge), apply(apply), leaf(leaf), dp(g.size(), leaf), memo(g.size(), leaf) { dfs1(0, -1); dfs2(0, -1, leaf); } const Data &operator[](int i) const { return dp[i]; } void dfs1(int cur, int p) { for(auto &d : g[cur]) { if(d.to == p) continue; dfs1(d.to, cur); memo[cur] = merge(memo[cur], apply(memo[d.to], d.to, cur, d.cost)); } } void dfs2(int cur, int p, const Data &val) { vector<Data> ds{val}; for(auto &d : g[cur]) { if(d.to == p) continue; ds.emplace_back(apply(memo[d.to], d.to, cur, d.cost)); } vector<Data> left(ds.size() + 1, leaf), right(ds.size() + 1, leaf); for(int i = 0; i + 1 < (int)left.size(); i++) left[i + 1] = merge(left[i], ds[i]); for(int i = ssize(right) - 2; 0 < i; i--) right[i] = merge(right[i + 1], ds[i]); dp[cur] = left.back(); int idx = 1; for(auto &d : g[cur]) { if(d.to == p) continue; Data tmp = merge(left[idx], right[idx + 1]); tmp = apply(tmp, cur, d.to, d.cost); dfs2(d.to, cur, tmp); idx++; } } }; #line 4 "/home/y_midori/cp/a.cpp" int main() { using Data = vi; using Cost = int; INT(n); Graph<Cost> g(n); g.read(n - 1); Data leaf = {0}; auto merge = [](Data a, Data b) { if(b.size() > a.size()) swap(a, b); if(b.empty()) return a; a.insert(end(a), begin(b), end(b)); return a; }; auto apply = [](Data data, int from, int to, Cost cost) { return Data({ranges::max(data) + 1}); }; Rerooting<Data, decltype(g), decltype(merge), decltype(apply)> dp( g, merge, apply, leaf); int ans = 0; for(auto &vi : dp.dp) { ranges::sort(vi, greater()); rep(i, ssize(vi)) { chmax<int>(ans, 1 + (i + 1) * vi[i]); } } print(ans); }