#include #include #include using namespace std; typedef long long ll; const ll MOD = 998244353; ll modpow(ll x, ll n){ ll res = 1, r = x; while(n){ if(n & 1) res = res * r % MOD; r = r * r % MOD; n >>= 1; } return res; } struct Tree { int n; int r; int l; std::vector> prit; std::vector> t; std::vector par; std::vector dpt; std::vector tour; std::vector> appear_on_tour; std::vector> anc; Tree(){} Tree(int n) : n(n){ prit.resize(n); t.resize(n); par.resize(n); dpt.resize(n); } void add_edge(int u, int v){ prit[u].push_back(v); prit[v].push_back(u); } void build(int r_){ r = r_; for(int i = 0; i < n; i++) dpt[i] = -1; std::queue que; par[r] = -1; dpt[r] = 0; que.push(r); while(que.size()){ int u = que.front(); que.pop(); for(int v : prit[u]){ if(dpt[v] == -1){ t[u].push_back(v); par[v] = u; dpt[v] = dpt[u] + 1; que.push(v); } } } } void rebuild(int r_){ for(int u = 0; u < n; u++) t[u].clear(); build(r_); } std::vector toposort(){ std::vector> p(n); for(int i = 0; i < n; i++) p[i] = std::pair(dpt[i], i); sort(p.begin(), p.end(), std::greater>()); std::vector res(n); for(int i = 0; i < n; i++) res[i] = p[i].second; return res; } void dfs(int u, int &k){ appear_on_tour[u].push_back(k); tour[k++] = u; for(int v : t[u]){ dfs(v, k); appear_on_tour[u].push_back(k); tour[k++] = u; } } void build_euler_tour(){ tour.resize(n * 2 - 1); appear_on_tour.resize(n); int k = 0; dfs(r, k); } void build_lca(){ for(l = 1; l <= n; l++){ if((1 << (l - 1)) >= n) break; } anc.resize(l); for(int j = 0; j < l; j++) anc[j].resize(n); for(int i = 0; i < n; i++) anc[0][i] = par[i]; for(int j = 1; j < l; j++){ for(int i = 0; i < n; i++){ if(anc[j - 1][i] == -1) anc[j][i] = -1; else anc[j][i] = anc[j - 1][anc[j - 1][i]]; } } } int lca(int u, int v){ if(dpt[u] < dpt[v]) std::swap(u, v); int dpt_diff = dpt[u] - dpt[v]; for(int j = l - 1; j >= 0; j--){ if((dpt_diff >> j) & 1) u = anc[j][u]; } if(u == v) return u; for(int j = l - 1; j >= 0; j--){ if(anc[j][u] != anc[j][v]){ u = anc[j][u]; v = anc[j][v]; } } return anc[0][u]; } }; void dfs(int u, int n, ll &s, ll *c, Tree &t){ for(int v : t.t[u]){ s = (s + c[v] * (n - c[v])) % MOD; dfs(v, n, s, c, t); } } int main() { int n; cin >> n; Tree t(n); for(int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; u--; v--; t.add_edge(u, v); } t.build(0); ll c[100005]{0}; vector p = t.toposort(); for(int i = 0; i < n; i++){ int u = p[i]; c[u] = 1; for(int v : t.t[u]) c[u] += c[v]; } ll s = 0; dfs(0, n, s, c, t); cout << (1 + MOD - s * modpow(n * (n - 1) * (n - 1) / 2 % MOD, MOD - 2) % MOD) % MOD << endl; }