#include #include #include #include #include using mint = atcoder::modint998244353; int edge_num(int n) { return (n * (n + 1)) >> 1; } auto find_path_on_tree(const std::vector> &g, int u, int v) { std::vector res; auto dfs = [&](auto dfs, int cur, int par) -> bool { res.push_back(cur); if (cur == v) return true; for (int nxt : g[cur]) if (nxt != par and dfs(dfs, nxt, cur)) return true; res.pop_back(); return false; }; dfs(dfs, u, -1); return res; } #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector> g(n); for (int i = 0; i < n - 1; ++i) { int u, v; std::cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } const int m = edge_num(n); const mint inv_m = mint(m).inv(); std::map, std::vector> paths; std::map, std::vector> compl_paths; std::map, std::pair> rev_paths; for (int x = 0; x < n; ++x) for (int y = 0; y <= x; ++y) { std::vector path = find_path_on_tree(g, x, y); std::sort(path.begin(), path.end()); std::vector compl_path; for (int i = 0, j = 0; i < n; ++i) { if (j < int(path.size()) and path[j] == i) { ++j; continue; } compl_path.push_back(i); } paths[std::make_pair(x, y)] = path; rev_paths[path] = std::make_pair(x, y); compl_paths[std::make_pair(x, y)] = compl_path; } std::map, mint> dp; auto rec = [&](auto rec, int x, int y) -> mint { if (auto it = dp.find(std::make_pair(x, y)); it != dp.end()) { return it->second; } mint a = 1, b = 1; std::vector path = paths[std::make_pair(x, y)]; for (const auto &[_, compl_path] : compl_paths) { std::vector next_path; std::set_difference(path.begin(), path.end(), compl_path.begin(), compl_path.end(), std::back_inserter(next_path)); if (next_path.size()) { if (next_path.size() == path.size()) { a -= inv_m; } else { auto [nx, ny] = rev_paths[next_path]; b += inv_m * rec(rec, nx, ny); } } } return dp[std::make_pair(x, y)] = b * a.inv(); }; mint ans = 1; for (int x = 0; x < n; ++x) for (int y = 0; y <= x; ++y) { ans += rec(rec, x, y) * inv_m; } std::cout << ans.val() << std::endl; return 0; }