from collections import deque from typing import List P = 998244353 def inv(n): return pow(n, P - 2, P) def edge_num(n: int): return (n * (n + 1)) >> 1 def solve(n: int, g: List[List[int]]): m = edge_num(n) inv_m = inv(m) par_ = [0] * n siz_ = [1] * n def precalc(u: int, p: int): par_[u] = p for v in g[u]: if v != p: siz_[u] += precalc(v, u) return siz_[u] precalc(0, -1) def subtree_size(u: int, p: int): if par_[u] == p: return siz_[u] else: return n - siz_[p] def calc_t_1(u: int, ng1: int): return n - subtree_size(ng1, u) def calc_t_2(u: int, ng1: int, ng2: int): return n - subtree_size(ng1, u) - subtree_size(ng2, u) ans_f = [0] * n for x in range(n): u_xx_x = m - sum(edge_num(subtree_size(y, x)) for y in g[x]) ans_f[x] = m * inv(m - u_xx_x) % P ans_g = [[0] * n for _ in range(n)] par = [[-1] * n for _ in range(n)] dq = deque() for x in range(n): ans_g[x][x] = ans_f[x] s_x_x = n u_xx_x = edge_num(n) - sum(edge_num(subtree_size(y, x)) for y in g[x]) for y in g[x]: s_x_y = subtree_size(y, x) u_xy_x = u_xx_x - s_x_y * (s_x_x - s_x_y) Axy = u_xy_x * ans_f[x] % P Bxy = 0 par[x][y] = x dq.append((x, y, Axy, Bxy)) while dq: x, y, Axy, Bxy = dq.popleft() par_y = par[x][y] s_x_y = subtree_size(y, par_y) u_xy_y = edge_num(s_x_y) - sum(edge_num(subtree_size(w, y)) for w in g[y] if w != par_y) t_xy_y = s_x_y ans_g[x][y] = (Axy + u_xy_y * ans_f[y] + Bxy) % P prev_z, z = y, par_y while z != x: next_z = par[x][z] t_xy_z = calc_t_2(z, prev_z, next_z) ans_g[x][y] = (ans_g[x][y] + t_xy_y * t_xy_z * ans_g[y][z]) % P prev_z, z = z, next_z t_xy_x = calc_t_1(x, prev_z) ans_g[x][y] = ((1 + ans_g[x][y] * inv_m) % P * inv(1 - (t_xy_x * t_xy_y * inv_m))) % P for w in g[y]: if w == par_y: continue t_xw_x = t_xy_x s_x_w = subtree_size(w, y) t_xw_y = t_xy_y - s_x_w u_xw_y = u_xy_y - s_x_w * (s_x_y - s_x_w) Axw = (Axy + u_xw_y * ans_f[y]) % P Bxw = (Bxy + t_xw_y * t_xw_x * ans_g[x][y]) % P prev_z, z = y, par_y while z != x: next_z = par[x][z] t_xw_z = calc_t_2(z, prev_z, next_z) Bxw = (Bxw + t_xw_y * t_xw_z * ans_g[y][z]) % P prev_z, z = z, next_z par[x][w] = y dq.append((x, w, Axw, Bxw)) ans = 1 for x in range(n): for y in range(x + 1): ans = (ans + ans_g[x][y] * inv_m) % P print(ans) n = int(input()) g = [[] for _ in range(n)] for _ in range(n - 1): u, v = map(int, input().split()) u -= 1 v -= 1 g[u].append(v) g[v].append(u) solve(n, g)