結果

問題 No.3373 Partial Complement Tree
コンテスト
ユーザー ぽえ
提出日時 2025-11-21 23:09:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 352 ms / 2,000 ms
コード長 9,023 bytes
コンパイル時間 3,525 ms
コンパイル使用メモリ 302,368 KB
実行使用メモリ 37,624 KB
最終ジャッジ日時 2025-11-21 23:10:05
合計ジャッジ時間 9,214 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef poe
#define debug(x) cerr<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pi=pair<int,int>;
using pll=pair<ll,ll>;
using str=string;
template<class T>using vec=vector<T>;
using vi=vec<int>;using vvi=vec<vi>;using vvvi=vec<vvi>;using vvvvi=vec<vvvi>;using vvvvvi=vec<vvvvi>;
using vll=vec<ll>;using vvll=vec<vll>;using vvvll=vec<vvll>;using vvvvll=vec<vvvll>;using vvvvvll=vec<vvvvll>;
using vpi=vec<pi>;using vvpi=vec<vpi>;using vvvpi=vec<vvpi>;using vvvvpi=vec<vvvpi>;using vvvvvpi=vec<vvvvpi>;
using vpll=vec<pll>;using vvpll=vec<vpll>;using vvvpll=vec<vvpll>;using vvvvpll=vec<vvvpll>;using vvvvvpll=vec<vvvvpll>;
template<class T>using pq=priority_queue<T,vector<T>>;
template<class T>using pqg=priority_queue<T,vector<T>,greater<T>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define loop(i, l, r) for (int i=(int)(l); i<(int)(r); i++)
#define per(i,n) for(int i=(int)(n)-1;0<=i;i--)
#define per1(i,n) for(int i=(int)(n);0<i;i--)
#define range(i,x) for(auto&i:x)
#define range2(i,j,x) for(auto&[i,j]:x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define Sort(x) sort((x).begin(),(x).end())
#define troS(x) sort((x).rbegin(),(x).rend())
#define Reverse(x) reverse((x).begin(),(x).end())
#define uniq(x) sort((x).begin(),(x).end());(x).erase(unique((x).begin(),(x).end()),(x).end())
#define nextp(x) next_permutation((x).begin(),(x).end())
#define nextc(x,k) next_combination((x).begin(),(x).end(),k)
#define bit(x,i) (((x)>>(i))&1)
#define pf push_front
#define pb push_back
#define df pop_front
#define db pop_back
#define fi first
#define se second
#define elif else if
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define YN(x) cout<<((x)?"Yes":"No")<<'\n'
#define O(x) cout<<(x)<<'\n'
#define ismid(a,b,c) ((a)<=(b)&&(b)<(c))
template<class S,class T>bool chmin(S&a,T b){if(a>b){a=b;return true;}return false;}
template<class S,class T>bool chmax(S&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool next_combination(T l,T r,int k){T m=l+k;if(l==r||l==m||r==m)return false;T t=m;while(l!=t){t--;if(*t<*(r-1)){T d=m;while(*t>=*d)d++;iter_swap(t,d);rotate(t+1,d+1,r);rotate(m,m+(r-d)-1,r);return true;}}rotate(l,m,r);return false;}
template<class T>T Min(T a,T b){return a<b?a:b;}
template<class T,class...Args>T Min(T a,T b,Args...args){return Min(Min(a,b),args...);}
template<class T>T Max(T a,T b){return a>b?a:b;}
template<class T,class...Args>T Max(T a,T b,Args...args){return Max(Max(a,b),args...);}
template<class T>T Sum(T a){return a;}
template<class T,class... Args>T Sum(T a,Args... args){return a+Sum(args...);}
template<class T>T Max(const vector<T>&v){return *max_element(all(v));}
template<class T>T Min(const vector<T>&v){return *min_element(all(v));}
template<class T>T Sum(const vector<T>&v){return accumulate(all(v),T(0));}
template<class S,class T>T Max(const pair<S,T>&p){return max(p.first,p.second);}
template<class S,class T>T Min(const pair<S,T>&p){return min(p.first,p.second);}
template<class S,class T>T Sum(const pair<S,T>&p){return p.first+p.second;}
template<class S,class T>istream&operator>>(istream&s,pair<S,T>&p){s>>p.first>>p.second;return s;}
template<class S,class T>ostream&operator<<(ostream&s,pair<S,T>&p){s<<p.first<<' '<<p.second<<'\n';return s;}
template<class T>istream&operator>>(istream&s,vector<T>&v){for(auto&i:v)s>>i;return s;}
template<class T>ostream&operator<<(ostream&s,vector<T>&v){for(int i=0;i<(int)v.size();i++)s<<v[i]<<" \n"[i==(int)v.size()-1];return s;}
const int dxy[5]={0,1,0,-1,0};
const int dx[8]={0,1,0,-1,1,1,-1,-1};
const int dy[8]={1,0,-1,0,1,-1,1,-1};
#define nl '\n'
#define sp ' '
const int inf = (1<<30)-(1<<15);
const ll INF = 1LL<<61;
const ll mod = 998244353;
const ll MOD = 1000000007;
const ld EPS = 1e-9;
const ld PI = acos(-1);

void IO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(30);
}

void solve();
// poe

// 辺の構造体 edge(from, to, cost, id)
template<class T = int>
struct edge {
    int from, to;
    T cost;
    int id;
};
// 頂点の構造体 vector<edge<T>>
template<class T = int>
using edges = vector<edge<T>>;
// グラフの構造体 graph<T, directed, weighted> 
template <class T = int, bool directed = false, bool weighted = false>
struct graph {
    bool isdirected, isweighted;
    edges<T> _edges;
    vector<edges<T>> data;
    T sumcost;
    graph() = default;
    // 頂点数 n のグラフを作成する
    graph(int n) : isdirected(directed), isweighted(weighted), data(n), sumcost(T{}) {}
    // from から to へ辺を追加する
    void add_edge(int from, int to, T cost = 1, int id = -1) {
        if (id == -1) id = _edges.size();
        data[from].push_back(edge<T>{from, to, cost, id});
        _edges.push_back(edge<T>{from, to, cost, id});
        if (!isdirected) {
            data[to].push_back(edge<T>{to, from, cost, id});
        }
        sumcost += cost;
    }
    // 辺を追加する
    void add_edge(edge<T> _e) {
        add_edge(_e.from, _e.to, _e.cost, _e.id);
    }
    // 標準入力から辺を読み込む
    void read(int m, int indexed = 1) {
        for (int i=0; i<m; i++) {
            int from, to;
            T cost = 1;
            cin >> from >> to;
            if (isweighted) cin >> cost;
            add_edge(from - indexed, to - indexed, cost);
        }
    }
    // 頂点数を返す
    int size() {
        return data.size();
    }
    // 頂点を返す
    edges<T> operator[](int k) {
        return data[k];
    }
    // パスを頂点に変換する
    vector<int> path_to_vertex(edges<T>& _e) {
        vector<int> re;
        if (_e.size() == 0) {
            return re;
        }
        if (_e.size() == 1) {
            re.push_back(_e[0].from);
            re.push_back(_e[0].to);
            return re;
        }
        int x=_e[0].from,y=_e[0].to;
        if (x==_e[1].to || x == _e[1].from) swap(x, y);
        re.push_back(x);
        for (int i=1; i<_e.size(); i++) {
            re.push_back(y);
            x = _e[i].to;
            if (x == y) x = _e[i].from;
            swap(x, y);
        }
        return re;
    }
    // 頂点をパスに変換する
    edges<T> vetex_to_path (vector<int>& v){
        edges<T> re;
        for (int i=0; i+1<v.size(); i++) {
            for (auto& _e : this[v[i]]) {
                if (_e.to == v[i+1]) {
                    re.push_back(_e);
                    break;
                }
            }
        }
        return re;
    }
};


template <class T = int, bool directed = false, bool weighted = false>
vector<int> dfs_order(graph<T, weighted, directed>& g, int s = 0) {
    vector<int> re(g.size(), -1);
    stack<int> q; q.push(s);
    int cnt = 0; re[s] = cnt++;
    while (!q.empty()) {
        int x = q.top(); q.pop();
        for (auto e : g[x]) {
            if (re[e.to] == -1) {
                re[e.to] = cnt++;
                q.push(e.to);
            }
        }
    }
    return re;
}

template <class T = int, bool directed = false, bool weighted = false>
vector<int> bfs_order(graph<T, weighted, directed>& g, int s = 0) {
    vector<int> re(g.size(), -1);
    queue<int> q; q.push(s);
    int cnt = 0; re[s] = cnt++;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (auto e : g[x]) {
            if (re[e.to] == -1) {
                re[e.to] = cnt++;
                q.push(e.to);
            }
        }
    }
    return re;
}

template <class T = int, bool directed = false, bool weighted = false>
vector<int> distance(graph<T, weighted, directed>& g, int s = 0) {
    vector<int> re(g.size(), -1);
    queue<int> q; q.push(s);
    re[s] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (auto e : g[x]) {
            if (re[e.to] == -1) {
                re[e.to] = re[x] + 1;
                q.push(e.to);
            }
        }
    }
    return re;
}

template <class T = int, bool directed = false, bool weighted = false>
pair<int, pair<int, int>> diameter(graph<T, weighted, directed>& g) {
    vector<int> d1 = distance(g, 0);
    int s = max_element(d1.begin(), d1.end()) - d1.begin();
    vector<int> d2 = distance(g, s);
    int t = max_element(d2.begin(), d2.end()) - d2.begin();
    return {d2[t], {s, t}};
}


int main() { IO();
    int T=1;
    cin >> T;
    while (T--) solve();
}

#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;

void solve() {
	int n; cin >> n;
	graph<int, false, false> g(n); g.read(n-1);
	mint ans = 0;
	vi b = bfs_order(g);
	vpi c(n); rep(i, n) c[i] = {b[i], i};
	troS(c);
	vi d = distance(g);
	vec<vec<mint>> dp(n, vec<mint>(4));
	range2(_, i, c) {
    dp[i][0] = 1;
    range(e, g[i]) if (d[i] < d[e.to]) {
      rep(j, 3) ans += dp[i][j] * dp[e.to][2-j];
      rep(j, 3) dp[i][j+1] += dp[e.to][j];
    }
  }
	cout << ans.val() << nl;
}
0