#1193734 (C++23) No.3206 う し た ウ ニ 木 あ く ん 笑

• 問題: No.3206 う し た ウ ニ 木 あ く ん 笑
• ユーザー: zawakasu
• 提出日時: 2026-10-19 16:00:21
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 151 ms / 3,000 ms
• コード長: 8,146 bytes
• コンパイル時間: 2,079 ms
• コンパイル使用メモリ: 233,276 KB
• 実行使用メモリ: 103,236 KB
• 最終ジャッジ日時: 2026-10-19 16:00:34
• 合計ジャッジ時間: 8,769 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge6_0

ファイルパターン	結果
sample	AC * 2
other	AC * 30

ソースコード

/*
 * Disclaimer: All code enclosed within “namespace zawa” is available at the following link.
 * https://zawa-tin.github.io/cp-documentation/
 */
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <random>
// #include "Src/Number/IntegerDivision.hpp"
// #include "Src/Utility/BinarySearch.hpp"
// #include "Src/Sequence/CompressedSequence.hpp"
// #include "Src/Sequence/RunLengthEncoding.hpp"
// #include "Src/Algebra/Group/AdditiveGroup.hpp"
// #include "Src/DataStructure/FenwickTree/FenwickTree.hpp"
// #include "Src/DataStructure/SegmentTree/SegmentTree.hpp"
// #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
// #include "Src/DataStructure/Heap/BinaryHeap.hpp"


#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept TreeDP = requires {
    typename T::Tree;
    typename T::Cluster;
    typename T::Edge;
    typename T::Vertex;
    { T::Convert(std::declval<typename T::Vertex>()) } -> std::same_as<typename T::Tree>;
    { T::AddEdge(std::declval<typename T::Tree>(), std::declval<typename T::Edge>()) } -> std::same_as<typename T::Cluster>;
    { T::Merge(std::declval<typename T::Cluster>(), std::declval<typename T::Cluster>()) } -> std::same_as<typename T::Cluster>;
    { T::AddVertex(std::declval<typename T::Cluster>(), std::declval<typename T::Vertex>()) } -> std::same_as<typename T::Tree>;
};

}

template <concepts::TreeDP DP,std::integral T>
class Rerooting {
public:

    using Tree = DP::Tree;

    using Cluster = DP::Cluster;

    using Edge = DP::Edge;

    using Vertex = DP::Vertex;

    Rerooting(usize n,std::vector<std::pair<T,T>> ed,std::vector<Vertex> vs,std::vector<Edge> es) 
    : m_n{n}, m_edges{std::move(ed)}, m_alls(n), m_sides(m_edges.size()) {
        assert(m_edges.size()+1==n); 
        assert(m_edges.size()==es.size());
        assert(n==vs.size());
        if (n==1) {
            m_alls[0]=DP::Convert(vs[0]);
            return;
        }
        std::vector<std::vector<std::pair<T,u32>>> g(n);
        for (usize i = 0 ; auto [u,v] : m_edges) {
            g[u].push_back({v,i});
            g[v].push_back({u,i});
            i++;
        }
        std::vector<Tree> dp(n);
        auto dfs1=[&](auto dfs,T v,T p) -> Tree {
            if (std::ssize(g[v])==1 and g[v][0].first==p)
                return dp[v]=DP::Convert(vs[v]);
            usize idx=g[v][0].first==p?1:0;
            assignToSides(dfs(dfs,g[v][idx].first,v),g[v][idx].second,g[v][idx].first);
            Cluster prod=DP::AddEdge(dp[g[v][idx].first],es[g[v][idx].second]);
            for (idx++ ; idx<g[v].size() ; idx++) 
                if (g[v][idx].first!=p) {
                    assignToSides(dfs(dfs,g[v][idx].first,v),g[v][idx].second,g[v][idx].first);
                    prod=DP::Merge(prod,DP::AddEdge(dp[g[v][idx].first],es[g[v][idx].second]));
                }
            return dp[v]=DP::AddVertex(std::move(prod),vs[v]);
        };
        dfs1(dfs1,0,static_cast<T>(0));
        auto dfs2=[&](auto dfs,T v,T p,Tree t) -> void {
            const usize k=g[v].size();
            std::vector<Cluster> clusters(k);
            for (usize i = 0 ; i < k ; i++) {
                if (g[v][i].first==p) {
                    assignToSides(t,g[v][i].second,p);
                    clusters[i]=DP::AddEdge(t,es[g[v][i].second]);
                }
                else
                    clusters[i]=DP::AddEdge(dp[g[v][i].first],es[g[v][i].second]);
            }
            if (k==1) {
                m_alls[v]=DP::AddVertex(clusters[0],vs[v]);
                if (g[v][0].first!=p) {
                    assert(!v);
                    dfs(dfs,g[v][0].first,v,DP::Convert(vs[v]));
                }
            }
            else {
                std::vector<Cluster> pref=clusters,suf=clusters;
                for (usize i = 1 ; i < k ; i++) {
                    pref[i]=DP::Merge(pref[i-1],clusters[i]);
                    suf[k-i-1]=DP::Merge(clusters[k-i-1],suf[k-i]);
                }
                m_alls[v]=DP::AddVertex(pref[k-1],vs[v]);
                for (usize i = 0 ; i < g[v].size() ; i++) 
                    if (g[v][i].first!=p) {
                        Cluster pc=i?(i+1<g[v].size()?DP::Merge(pref[i-1],suf[i+1]):pref[k-2]):suf[1];
                        dfs(dfs,g[v][i].first,v,DP::AddVertex(pc,vs[v]));
                    }
            }
        };
        dfs2(dfs2,0,static_cast<T>(0),Tree{});
    }

    inline usize size() const noexcept {
        return m_n;
    }

    const Tree& operator[](usize i) const noexcept {
        assert(i < size());
        return m_alls[i];
    }

    const Tree& side(usize i,T v) const {
        assert(i < m_sides.size()); 
        if (m_edges[i].first==v)
            return m_sides[i].first;
        else if (m_edges[i].second==v)
            return m_sides[i].second;
        assert(0);
        return m_sides[i].first;
    }

private:

    void assignToSides(Tree t,usize idx,T v) {
        if (m_edges[idx].first==v)
            m_sides[idx].first=std::move(t);
        else
            m_sides[idx].second=std::move(t);
    }

    usize m_n;

    std::vector<std::pair<T,T>> m_edges;

    std::vector<Tree> m_alls;

    std::vector<std::pair<Tree,Tree>> m_sides;

};

} // namespace zawa
namespace zawa {}
using namespace zawa;
// #include "atcoder/modint"
// using mint = atcoder::modint998244353;
// #include <array>
// #include <bit>
// #include <bitset>
// #include <climits>
// #include <cmath>
// #include <set>
// #include <unordered_set>
// #include <map>
// #include <unordered_map>
// #include <optional>
// #include <queue>
// #include <stack>
// #include <deque>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0 ; i < ssize(v) ; i++)
        os << v[i] << (i + 1 == ssize(v) ? "" : " ");
    return os;
}
/*
 *
 */
struct DP {
    using Tree = int;
    using Cluster = int;
    using Edge = struct {};
    using Vertex = struct {};
    static Tree Convert(Vertex) {
        return 1;
    }
    static Cluster AddEdge(Tree t,Edge) {
        return t+1;
    }
    static Cluster Merge(Cluster l,Cluster r) {
        return max(l,r);
    }
    static Tree AddVertex(Cluster c,Vertex) {
        return c;
    }
};
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
#if !defined DEBUG
    int N;
    cin >> N;
    vector<pair<int,int>> E(N-1);
    vector<vector<pair<int,int>>> G(N);
    for (int i = 0 ; auto& [u,v] : E) {
        cin >> u >> v;
        u--; v--;
        G[u].push_back({v,i});
        G[v].push_back({u,i});
        i++;
    }
    Rerooting<DP,int> dp(N,E,vector<DP::Vertex>(N),vector<DP::Edge>(N-1));
    int ans=0;
    for (int v = 0 ; v < N ; v++) {
        vector<int> paths;
        for (auto [x,i] : G[v]) 
            paths.push_back(dp.side(i,x));
        ranges::sort(paths);
        int cnt=ssize(paths);
        for (int j : paths) {
            ans=max(ans,j*cnt+1);
            cnt--;
        }
    }
    cout << ans << '\n';
#else
    mt19937_64 mt{random_device{}()};
    for (int testcase = 0 ; ; ) {
        cerr << "----------" << ++testcase << "----------" << endl;
        
        auto a = solve(), b = naive();
        if (a != b) {
            // print testcase

            cerr << "you: " << a << endl;
            cout << "correct: " << b << endl;
            exit(0);
        }
    }
#endif
}