結果

問題 No.3373 Partial Complement Tree
コンテスト
ユーザー butsurizuki
提出日時 2025-11-21 21:40:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 852 bytes
コンパイル時間 2,777 ms
コンパイル使用メモリ 279,024 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2025-11-21 21:40:24
合計ジャッジ時間 5,015 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
const ll mod=998244353;

// v, Ke, maxTe
// 1  0  0 ... invalid
// 2  1  1 ... invalid (Ke is odd)
// 3  3  2 ... invalid (Ke is odd)
// 4  6  3
// 5  10 4 ... invalid
// >5 ... invalid

// tree of size 4 ...
// a-b a-c a-d ... can't flip
// a-b b-c c-d ... can flip

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    ll n;
    cin >> n;
    vector<ll> u(n),v(n);
    vector<ll> deg(n,0);
    for(ll i=1;i<n;i++){
      cin >> u[i] >> v[i];
      u[i]--; v[i]--;
      deg[u[i]]++;
      deg[v[i]]++;
    }
    ll res=0;
    for(ll i=1;i<n;i++){
      deg[u[i]]--;
      deg[v[i]]--;
      res+=(deg[u[i]]*deg[v[i]]);
      res%=mod;
      deg[u[i]]++;
      deg[v[i]]++;
    }
    cout << res%mod << "\n";
  }
  return 0;
}
0