結果

問題 No.3373 Partial Complement Tree
コンテスト
ユーザー DeltaStruct
提出日時 2025-11-21 22:07:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 296 ms / 2,000 ms
コード長 699 bytes
コンパイル時間 1,738 ms
コンパイル使用メモリ 203,032 KB
実行使用メモリ 38,976 KB
最終ジャッジ日時 2025-11-21 22:07:26
合計ジャッジ時間 7,726 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;

int main(){
  int q; cin >> q;
  while(q--){
    int n; cin >> n; vector<vector<int>> G(n); for (int i(1),a,b;i < n;++i){
      cin >> a >> b; G[a-1].emplace_back(b-1),G[b-1].emplace_back(a-1);
    }
    mint r = 0;
    auto dfs = [&](auto dfs,int x,int p) -> vector<mint> {
      vector<mint> R(4); R[0] = 1;
      for (int y:G[x]) if (y!=p){
        vector<mint> T = dfs(dfs,y,x);
        r += R[2]*T[0]+R[1]*T[1]+T[2];
        for (int k(0);k < 3;++k) R[k+1] += T[k];
      }
      return vector<mint>(R.begin(),R.end()-1);
    };
    dfs(dfs,0,-1);
    cout << r.val() << endl;
  }
}
0