結果

問題 No.3346 Tree to DAG
コンテスト
ユーザー 2251799813685248
提出日時 2025-11-14 00:50:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 6,559 bytes
コンパイル時間 1,403 ms
コンパイル使用メモリ 130,060 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2025-11-14 00:50:20
合計ジャッジ時間 5,578 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>


using namespace std;
#define ll long long
#define MOD 998244353
#define ld long double
#define INF 2251799813685248
#define vall(A) A.begin(),A.end()
#define gridinput(vv,H,W) for (ll i = 0; i < H; i++){string T; cin >> T; for(ll j = 0; j < W; j++){vv[i][j] = {T[j]};}}
#define adjustedgridinput(vv,H,W) for (ll i = 1; i <= H; i++){string T; cin >> T; for(ll j = 1; j <= W; j++){vv[i][j] = {T[j-1]};}}
#define vin(A) for (ll i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}
#define vout(A) for(ll i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define adjustedvin(A) for (ll i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}
#define adjustedvout(A) for(ll i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define vout2d(A,H,W) for (ll i = 0; i < H; i++){for (ll j = 0; j < W; j++){cout << A[i][j] << " \n"[j==W-1];}}
#define encode(i,j) ((i)<<32)+j
#define decode(v,w) (w ? (v)%4294967296 : (v)>>32)
vector<ll> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296};
vector<ll> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};

/**
 * @brief ビット（指数）のリストを受け取り、繰り上がり（2^k + 2^k = 2^{k+1}）
 * を全て処理して正規化された（重複のない）ビットリストを返す。
 * * 例: [5, 5, 3] -> [6, 3]
 * [5, 5, 6] -> [7]
 * * @param bits ビット（指数）のリスト。
 * Pythonと異なり、この関数内でソートするために
 * 値渡し（コピー）で受け取ります。
 * @return std::vector<ll> 正規化されたビットのリスト。
 */
std::vector<ll> normalize_bits(std::vector<ll> bits) {
    if (bits.empty()) {
        return {}; // 空のベクターを返す
    }

    // bits_sorted = sorted(bits, reverse=True)
    // 入力ベクター（のコピー）を降順にソート
    std::sort(bits.begin(), bits.end(), std::greater<ll>());

    std::vector<ll> stack;
    
    // for b in bits_sorted:
    for (ll b : bits) {
        // while len(stack) > 0 and stack[-1] == b:
        while (!stack.empty() && stack.back() == b) {
            // b = stack.pop() + 1
            b = stack.back() + 1;
            stack.pop_back(); // Pythonの .pop() に相当
        }
        // stack.append(b)
        stack.push_back(b);
    }

    return stack;
}

/**
 * @brief 非負整数の3つ組 (a,b,c) と (d,e,f) を受け取り、
 * F(a,b,c) = (2^{a+1}+2^{b+1}+2^{c+1}-3) / 2^{a+b+c}
 * F(d,e,f) = (2^{d+1}+2^{e+1}+2^{f+1}-3) / 2^{d+e+f}
 * の大小を比較する。
 * * @param abc (a, b, c) を含むベクター
 * @param def (d, e, f) を含むベクター
 * @return int 
 * 1 : F(a,b,c) > F(d,e,f)
 * 0 : F(a,b,c) == F(d,e,f)
 * -1 : F(a,b,c) < F(d,e,f)
 */
int compare_fractions(const std::vector<ll>& abc, const std::vector<ll>& def) {
    // a, b, c = abc
    ll a = abc[0];
    ll b = abc[1];
    ll c = abc[2];

    // d, e, f = def_
    ll d = def[0];
    ll e = def[1];
    ll f = def[2];

    // A = a + b + c
    // C++17以降の場合:
    // ll A = std::reduce(abc.begin(), abc.end());
    // ll D = std::reduce(def.begin(), def.end());
    // C++11互換:
    ll A = a + b + c;
    ll D = d + e + f;

    // 方針2で導出した両辺の指数リストを作成
    std::vector<ll> lhs_bits = {
        a + 1 + D,
        b + 1 + D,
        c + 1 + D,
        A + 1,
        A
    };

    std::vector<ll> rhs_bits = {
        d + 1 + A,
        e + 1 + A,
        f + 1 + A,
        D + 1,
        D
    };

    // 方針3: ビットリストを正規化
    std::vector<ll> norm_lhs = normalize_bits(lhs_bits);
    std::vector<ll> norm_rhs = normalize_bits(rhs_bits);

    // 方針4: 正規化済みリストを辞書順に比較
    // std::vector の比較演算子は辞書順比較をサポートしています。
    if (norm_lhs < norm_rhs) {
        return 1;
    } else {
        return 0;
    }
}


/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a 
/// @param b 
/// @param m 
/// @return a^b%m
ll modpow(ll a, ll b, ll m){
    ll t = a;
    ll ans = 1;
    while (b > 0){
        if (b%2){
            ans = (ans*t)%m;
        }
        b /= 2;
        t = (t*t)%m;
    }
    return ans;
}


void dfs(vector<vector<ll>> &E, vector<ll> &D, ll now){
    for (auto v : E[now]){
        if (D[v] != -1){
            continue;
        }
        D[v] = D[now]+1;
        dfs(E,D,v);
    }
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll N;
    cin >> N;
    vector<vector<ll>> E(N+1);
    for (ll i = 0; i < N-1; i++){
        ll u,v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    vector<ll> D(N+1,-1);
    vector<ll> D2(N+1,-1);
    vector<ll> D3(N+1,-1);
    D[1] = 0;
    dfs(E,D,1);
    ll dist_max_v = -1;
    ll d_max = -1;
    for (ll i = 1; i <= N; i++){
        if (D[i] >= d_max){
            d_max = D[i];
            dist_max_v = i;
        }
    }

    D2[dist_max_v] = 0;
    dfs(E,D2,dist_max_v);
    ll dist_max_v2 = -1;
    d_max = -1;
    for (ll i = 1; i <= N; i++){
        if (D2[i] >= d_max){
            d_max = D2[i];
            dist_max_v2 = i;
        }
    }

    D3[dist_max_v2] = 0;
    dfs(E,D3,dist_max_v2);


    ll diameter = D2[dist_max_v2];
    
    vector<ll> tempans({0,0,0,-1});
    
    for (ll i = 1; i <= N; i++){
        if (i == dist_max_v || i == dist_max_v2){continue;}
        ll l = D2[i] + D3[i] - diameter;
        l /= 2;
        ll k = D3[i]-l;
        ll m = D2[i]-l;
        ll answer = modpow(2,N+2,MOD) - modpow(2,N-k-l-m,MOD)*((2*(modpow(2,k,MOD) + modpow(2,l,MOD) + modpow(2,m,MOD))-3)%MOD);
        answer %= MOD;
        answer += MOD;
        answer %= MOD;
        vector<ll> temp{k,l,m, answer};
        if (!compare_fractions({tempans[0],tempans[1],tempans[2]},{k,l,m})){
            tempans = temp;
        }
    }



    cout << tempans.back() << "\n";
}
0