結果
問題 | No.1507 Road Blocked |
ユーザー | nawawan |
提出日時 | 2021-05-14 23:28:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 3,110 bytes |
コンパイル時間 | 747 ms |
コンパイル使用メモリ | 77,432 KB |
実行使用メモリ | 18,988 KB |
最終ジャッジ日時 | 2024-10-02 05:22:27 |
合計ジャッジ時間 | 6,007 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 79 ms
18,988 KB |
testcase_04 | AC | 112 ms
11,136 KB |
testcase_05 | AC | 105 ms
11,264 KB |
testcase_06 | AC | 104 ms
11,180 KB |
testcase_07 | AC | 112 ms
11,264 KB |
testcase_08 | AC | 109 ms
11,264 KB |
testcase_09 | AC | 129 ms
11,160 KB |
testcase_10 | AC | 128 ms
11,136 KB |
testcase_11 | AC | 122 ms
11,136 KB |
testcase_12 | AC | 110 ms
11,224 KB |
testcase_13 | AC | 114 ms
11,176 KB |
testcase_14 | AC | 118 ms
11,136 KB |
testcase_15 | AC | 112 ms
11,264 KB |
testcase_16 | AC | 111 ms
11,264 KB |
testcase_17 | AC | 109 ms
11,264 KB |
testcase_18 | AC | 110 ms
11,100 KB |
testcase_19 | AC | 113 ms
11,264 KB |
testcase_20 | AC | 110 ms
11,264 KB |
testcase_21 | AC | 108 ms
11,136 KB |
testcase_22 | AC | 111 ms
11,136 KB |
testcase_23 | AC | 107 ms
11,136 KB |
testcase_24 | AC | 114 ms
11,264 KB |
testcase_25 | AC | 109 ms
11,136 KB |
testcase_26 | AC | 111 ms
11,264 KB |
testcase_27 | AC | 111 ms
11,136 KB |
testcase_28 | AC | 107 ms
11,136 KB |
testcase_29 | AC | 106 ms
11,152 KB |
testcase_30 | AC | 109 ms
11,136 KB |
testcase_31 | AC | 110 ms
11,232 KB |
testcase_32 | AC | 108 ms
11,128 KB |
ソースコード
#include <iostream>#include <vector>#include <queue>using namespace std;template<const int MOD> struct modint{long long val;modint(): val(0) {}modint(long long x){if(x < 0) val = x % MOD + MOD;else val = x % MOD;}modint(const modint &t){val = t.val;}modint& operator =(const modint m){val = m.val;return *this;}modint operator -(){return modint(-val);}modint& operator-=(const modint &m){val -= m.val;if(val < 0) val += MOD;return *this;}modint& operator+=(const modint &m){val += m.val;if(val >= MOD) val -= MOD;return *this;}modint& operator*=(const modint &m){val *= m.val;val %= MOD;return *this;}modint& operator/=(modint m){*this *= m.inv();return *this;}modint inv(){long long x = 1, y = 0;long long a = val, b = MOD;while(b != 0){long long t = a / b;a -= t * b;x -= t * y;swap(a, b);swap(x, y);}x %= MOD;if(x < 0) x += MOD;return modint(x);}modint pow(long long k){long long res = 1;long long v = val;while(k > 0){if(k & 1) res = res * v % MOD;v = v * v % MOD;k >>= 1;}return modint(res);}modint operator==(const modint &m){return val == m.val;}modint operator+(const modint &m){return modint(*this) += m;}modint operator-(const modint &m){return modint(*this) -= m;}modint operator*(const modint &m){return modint(*this) *= m;}modint operator/(const modint &m){return modint(*this) /= m;}bool operator!=(const modint &m){return modint(*this).val != m.val;}bool operator!=(const int &m){return modint(*this).val != m;}};const int MOD = 998244353;using mint = modint<MOD>;long long dfs(int now, int par, vector<vector<int>>&G, vector<long long>&depth, vector<long long>&cnt){for(int t: G[now]){if(t != par){depth[t] = depth[now] + 1;cnt[now] += dfs(t, now, G, depth, cnt);}}cnt[now]++;return cnt[now];}int main(){long long N;cin >> N;vector<vector<int>> G(N);vector<int> A(N - 1), B(N - 1);for(int i = 0; i < N - 1; i++){int a, b;cin >> a >> b;a--;b--;G[a].push_back(b);G[b].push_back(a);A[i] = a;B[i] = b;}mint bo = N * (N - 1) / 2 * (N - 1);vector<long long> depth(N), cnt(N);dfs(0, -1, G, depth, cnt);mint si = 0;for(int i = 0; i < N - 1; i++){if(depth[A[i]] > depth[B[i]]){si += (N - cnt[A[i]]) * cnt[A[i]];}else{si += (N - cnt[B[i]]) * cnt[B[i]];}}si = bo - si;bo = bo.inv();cout << (bo * si).val << endl;}