結果
問題 | No.1507 Road Blocked |
ユーザー | magsta |
提出日時 | 2021-04-07 10:19:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 1,398 bytes |
コンパイル時間 | 842 ms |
コンパイル使用メモリ | 89,736 KB |
実行使用メモリ | 19,712 KB |
最終ジャッジ日時 | 2024-06-22 04:51:04 |
合計ジャッジ時間 | 5,176 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 79 ms
19,712 KB |
testcase_04 | AC | 93 ms
10,496 KB |
testcase_05 | AC | 85 ms
10,368 KB |
testcase_06 | AC | 85 ms
10,368 KB |
testcase_07 | AC | 87 ms
10,368 KB |
testcase_08 | AC | 92 ms
10,448 KB |
testcase_09 | AC | 90 ms
10,496 KB |
testcase_10 | AC | 90 ms
10,496 KB |
testcase_11 | AC | 92 ms
10,360 KB |
testcase_12 | AC | 88 ms
10,368 KB |
testcase_13 | AC | 91 ms
10,496 KB |
testcase_14 | AC | 84 ms
10,368 KB |
testcase_15 | AC | 85 ms
10,368 KB |
testcase_16 | AC | 82 ms
10,496 KB |
testcase_17 | AC | 90 ms
10,368 KB |
testcase_18 | AC | 90 ms
10,496 KB |
testcase_19 | AC | 91 ms
10,368 KB |
testcase_20 | AC | 97 ms
10,368 KB |
testcase_21 | AC | 90 ms
10,496 KB |
testcase_22 | AC | 101 ms
10,368 KB |
testcase_23 | AC | 102 ms
10,368 KB |
testcase_24 | AC | 98 ms
10,496 KB |
testcase_25 | AC | 96 ms
10,368 KB |
testcase_26 | AC | 93 ms
10,368 KB |
testcase_27 | AC | 92 ms
10,496 KB |
testcase_28 | AC | 89 ms
10,368 KB |
testcase_29 | AC | 90 ms
10,496 KB |
testcase_30 | AC | 94 ms
10,408 KB |
testcase_31 | AC | 89 ms
10,496 KB |
testcase_32 | AC | 85 ms
10,296 KB |
ソースコード
#include <iostream> #include <string> #include <algorithm> #include <utility> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue> #include <vector> using namespace std; using Graph = vector<vector<int>>; #define MOD 998244353 vector<long long> depth; vector<long long> subtree_size; void dfs(const Graph& G, int v, int p, int d) { depth[v] = d; for (auto nv : G[v]) { if (nv == p) continue; dfs(G, nv, v, d + 1); } subtree_size[v] = 1; for (auto c : G[v]) { if (c == p) continue; subtree_size[v] += subtree_size[c]; } } long long modinv(long long a, long long mod) { long long b = mod, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } int main() { long long N; cin >> N; Graph G(N); for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; G[a - 1].push_back(b - 1); G[b - 1].push_back(a - 1); } depth.assign(N, 0); subtree_size.assign(N, 0); dfs(G, 0, -1, 0); long long sum = 0; for (int i = 1; i < N; i++) sum += (N * (N - 1) / 2 - subtree_size[i] * (N - subtree_size[i])) % MOD; sum = sum % MOD * modinv(N * (N - 1) / 2, MOD) % MOD * modinv(N - 1, MOD) % MOD; cout << sum << endl; }