結果
問題 | No.1507 Road Blocked |
ユーザー |
![]() |
提出日時 | 2021-05-14 23:06:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,568 bytes |
コンパイル時間 | 646 ms |
コンパイル使用メモリ | 72,704 KB |
実行使用メモリ | 18,244 KB |
最終ジャッジ日時 | 2024-10-02 03:49:14 |
合計ジャッジ時間 | 4,038 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
//(A, B)ごとに数えると「平均パス長」だが、Eごとに数えると、Eで分離される2領域のサイズの積を単に足すだけになる。 //これ面白い。ただ、「平均パス長」を聞かれた方が、Eの項が隠される分、線形性が見えにくくなるから、よりテクニカルに見えるかも。 //期待値の線形性の練習としては、この問題の方が適切に見える。 #include <iostream> #include <vector> #include <algorithm> #define int long long using namespace std; int powmod(int a, int n, int mod) { if (n == 0) return 1; if (n % 2 == 1) return a * powmod(a, n - 1, mod) % mod; return powmod((a * a) % mod, n / 2, mod); } int n; int from[100000], to[100000]; vector<int> et[100000]; int sub_tree_size[100000]; int parent[100000]; int dfs(int p, int v) { int ret = 1; parent[v] = p; for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; if (nv == p) continue; ret += dfs(v, nv); } return sub_tree_size[v] = ret; } signed main() { int i; cin >> n; for (i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; et[u].push_back(v); et[v].push_back(u); from[i] = u; to[i] = v; } dfs(-1, 0); int setudan = 0; for (i = 0; i < n - 1; i++) { int u = from[i]; int v = to[i]; if (parent[u] == v) swap(u, v); int sz = sub_tree_size[v]; setudan += sz * (n - sz); } int all = n * (n - 1) / 2 * (n - 1); int mod = 998244353; int ans = (all - setudan) % mod * powmod(all % mod, mod - 2, mod) % mod; cout << ans << endl; return 0; }