結果

問題 No.3346 Tree to DAG
コンテスト
ユーザー AK_Mi
提出日時 2025-11-14 00:19:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,909 bytes
コンパイル時間 5,000 ms
コンパイル使用メモリ 261,912 KB
実行使用メモリ 18,304 KB
最終ジャッジ日時 2025-11-14 00:20:08
合計ジャッジ時間 8,300 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
ll dfs(ll x, ll g, vector<vector<ll>> &pass, vector<ll> &come){
    if(x == g){
        come[x] = 0;
        return 0;
    }
    come[x] = 0;
    for(ll i : pass[x]){
        
        if(come[i] >= 0)continue;
        ll num = dfs(i,g,pass,come);
        if(num != -1){
            come[x] = num + 1;
            return come[x];
        }
        
    }
    come[x] = -1;

    return -1;
}
int main(){
    ll n;
    ll p1,p2;
    cin >> n;

    vector<vector<ll>> pass(n,vector<ll>(0));
    ll u,v;

    for(ll i = 0; i < n-1; i++){
        cin >> u >> v;
        u--;
        v--;
        pass[u].push_back(v);
        pass[v].push_back(u);
    }

    queue<ll> bfs;
    vector<ll> come1(n,-1);
    come1[0] = 0;
    bfs.push(0);

    pair<ll,ll> maxx = {0,0};
    while(!bfs.empty()){
        ll x = bfs.front();
        bfs.pop();

        for(ll i : pass[x]){
            if(come1[i] >= 0)continue;
            come1[i] = come1[x] + 1;
            if(maxx.first < come1[i]){
                maxx = {come1[i],i};
            }
            bfs.push(i);
        }
    }

    p1 = maxx.second;
    maxx = {0,0};
    vector<ll> come2(n,-1);
    come2[p1] = 0;
    bfs.push(p1);
    
    while(!bfs.empty()){
        ll x = bfs.front();
        bfs.pop();

        for(ll i : pass[x]){
            if(come2[i] >= 0)continue;
            come2[i] = come2[x] + 1;
            if(maxx.first < come2[i]){
                maxx = {come2[i],i};
            }
            bfs.push(i);
        }
    }

    p2 = maxx.second;
    ll l = maxx.first;
    vector<ll> come3(n,-1);
    ll o = dfs(p1,p2,pass,come3);
    vector<ll> come4(n,-1);

    for(ll i = 0; i < n; i++){
        if(come3[i] >= 0){
            come3[i] = abs(come3[i]*2 - l);
            come4[i] = 0;
            bfs.push(i);
        }
    }

    tuple<ll,ll,ll> mm = {0,0,0};
    if(l % 2 == 1)get<2>(mm) = 1;
    else get<2>(mm) = 0;

    while(!bfs.empty()){
        ll x = bfs.front();
        bfs.pop();

        for(ll i : pass[x]){
            if(come4[i] >= 0)continue;
            come4[i] = come4[x] + 1;
            come3[i] = come3[x];
            if(get<0>(mm) < come4[i]){
                mm = {come4[i],i,come3[i]};
            }else if(get<0>(mm) == come4[i] && get<2>(mm) > come3[i]){
                mm = {come4[i],i,come3[i]};
            }
            bfs.push(i);
        }
    }

    ll a = (l + get<2>(mm))/2;
    ll b = (l - get<2>(mm))/2;
    ll c = get<0>(mm);
    ll d = n-1-a-b-c;

    
    vector<ll> two(n+1,1);
    for(ll i = 1; i <= n; i++){
        two[i] = (two[i-1] * 2)% 998244353;
    }

    ll ans = 998244353 + two[n-1] * 8;
    ans -= (two[d+1] * ((two[a+1]+two[b+1]+two[c+1] - 3)% 998244353))% 998244353;
    ans %= 998244353;
    
    cout << ans << '\n';

    return 0;
}
0