//(A, B)ごとに数えると「平均パス長」だが、Eごとに数えると、Eで分離される2領域のサイズの積を単に足すだけになる。 //これ面白い。ただ、「平均パス長」を聞かれた方が、Eの項が隠される分、線形性が見えにくくなるから、よりテクニカルに見えるかも。 //期待値の線形性の練習としては、この問題の方が適切に見える。 #include #include #include #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 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; }