結果

問題 No.3346 Tree to DAG
コンテスト
ユーザー n_bitand_n_per_3
提出日時 2025-11-01 09:34:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,724 bytes
コンパイル時間 7,148 ms
コンパイル使用メモリ 457,492 KB
実行使用メモリ 18,820 KB
最終ジャッジ日時 2025-11-13 21:11:24
合計ジャッジ時間 9,253 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 3 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
using boost::multiprecision::cpp_int;

// 意図的に非効率な O(N^2) に近い（最悪ノード訪問が O(N^2) になる）
// 「各頂点 r に対して、その隣接成分ごとに DFS を行って最遠距離を求める」
// という愚直実装。
// 正しさは保ちつつ計算量を落とさない（意図的）実装例。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<vector<int>> g(N+1);
    for (int i = 0; i < N-1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // pow2 (mod) 準備
    int MAXP = N + 10;
    vector<ll> pow2(MAXP+1);
    pow2[0] = 1;
    for (int i = 1; i <= MAXP; ++i) pow2[i] = (pow2[i-1] * 2) % MOD;

    auto modnorm = [&](ll x)->ll{
        x %= MOD;
        if (x < 0) x += MOD;
        return x;
    };

    // 最良解を保持（大きさ比較用に任意精度整数、出力は mod）
    cpp_int best_big = 0;
    ll best_mod = 0;
    bool best_set = false;

    // タイムスタンプ法で visited を管理（各 DFS ごとに初期化を避ける）
    vector<int> seen(N+1, 0);
    int cur_time = 1;

    // 各頂点 r を会合点として愚直に調べる
    for (int r = 1; r <= N; ++r) {
        vector<int> comps; // r から見た各成分の距離（0 を含める）
        comps.reserve(g[r].size() + 1);
        comps.push_back(0); // r 自身を選ぶ候補

        // 各隣接成分ごとに DFS をして r からの最遠距離を求める
        for (int v : g[r]) {
            // DFS starting at v, but never visit r
            int maxd = 0;
            ++cur_time;
            // mark r as seen for this DFS to block going back
            seen[r] = cur_time;
            // iterative stack (node, depth)
            stack<pair<int,int>> st;
            st.push({v, 1});
            seen[v] = cur_time;
            while (!st.empty()) {
                auto [u, d] = st.top(); st.pop();
                if (d > maxd) maxd = d;
                for (int w : g[u]) {
                    if (seen[w] != cur_time) {
                        seen[w] = cur_time;
                        st.push({w, d+1});
                    }
                }
            }
            comps.push_back(maxd);
        }

        if ((int)comps.size() < 3) continue; // 3つ取れないならスキップ

        // 上位3つを取る（降順ソートして先頭3つ）
        sort(comps.begin(), comps.end(), greater<int>());
        int x = comps[0], y = comps[1], z = comps[2];
        int s = x + y + z;

        int exp = (N - 1) - s;
        if (exp < 0) continue; // 無効な選択（理論上ありえないかもしれないが安全対策）

        // g mod と f mod
        ll term1 = pow2[s + 3];
        ll term2 = (pow2[x + 2] + pow2[y + 2]) % MOD;
        term2 += pow2[z + 2]; term2 %= MOD;
        ll gmod = modnorm(term1 - term2 + 6);
        ll fmod = (pow2[exp] * gmod) % MOD;

        // 正確な比較のために任意精度整数でも f を計算
        cpp_int g_big = cpp_int(1);
        g_big <<= (s + 3);
        g_big -= (cpp_int(1) << (x + 2));
        g_big -= (cpp_int(1) << (y + 2));
        g_big -= (cpp_int(1) << (z + 2));
        g_big += 6;
        if (g_big < 0) continue; // 安全対策

        cpp_int f_big = g_big << exp;

        if (!best_set || f_big > best_big) {
            best_set = true;
            best_big = f_big;
            best_mod = fmod;
        }
    }

    cout << (best_mod % MOD) << "\n";
    return 0;
}
0