結果

問題 No.3373 Partial Complement Tree
コンテスト
ユーザー ゼリトキ
提出日時 2025-11-21 22:30:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 281 ms / 2,000 ms
コード長 1,979 bytes
コンパイル時間 2,836 ms
コンパイル使用メモリ 282,520 KB
実行使用メモリ 44,928 KB
最終ジャッジ日時 2025-11-21 22:32:35
合計ジャッジ時間 8,133 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long mod=998244353;
const long long mod2=567629137;
ll power(ll a,ll b,ll m){//a^b
    a%=m;
    ll p=a,Answer=1;
    for(ll i=0;i<60;i++){
        ll wari=(1LL<<i);
        if((b/wari)%2==1){
            Answer=(Answer*p)%m;
        }
        p=(p*p)%m;
    }
    return Answer;
}
ll Division(ll a,ll b,ll m){//a/b
    return (a*power(b,m-2,m))%m;
}
void solve(){
    int N;
    cin>>N;
    int U[N],V[N];
    vector<int>G[N+1];
    for(int i=1;i<N;i++){
        cin>>U[i]>>V[i];
        G[U[i]].push_back(V[i]);
        G[V[i]].push_back(U[i]);
    }
    ll cnt[N+1][4];
    ll ans=0;
    bool already[N+1];
    for(int i=1;i<=N;i++){
        for(int j=0;j<4;j++) cnt[i][j]=0;
        cnt[i][1]=1;
        already[i]=0;
    }
    function<void(int)>dfs=[&](int pos){
        already[pos]=1;
        ll dat[4];
        for(int i=0;i<4;i++) dat[i]=0;
        for(int i=0;i<G[pos].size();i++){
            int nex=G[pos][i];
            if(already[nex]) continue;
            dfs(nex);
            for(int j=0;j<4;j++) dat[j]=(dat[j]+cnt[nex][j])%mod;
        }
        cnt[pos][1]=dat[0]+1;
        cnt[pos][2]=dat[1];
        cnt[pos][3]=dat[2];
        ans=(ans+dat[3])%mod;
        ll plus=0;
        for(int i=0;i<G[pos].size();i++){
            int nex=G[pos][i];
            if(already[nex]) continue;
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){
                    ll now_cnt=cnt[nex][j]*(dat[k]-cnt[nex][k]);
                    ll now_pos=(j+k+1)%4;
                    if(now_pos==0) plus=(plus+now_cnt)%mod;
                }
            }
        }
        plus=Division(plus,2,mod);
        ans=(ans+plus)%mod;
        already[pos]=0;
        return;
    };
    dfs(1);
    cout<<ans<<endl;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();

}
0