#include #include using namespace std; using ll = long long; const ll MOD = 998244353; using boost::multiprecision::cpp_int; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; if (!(cin >> N)) return 0; vector> g(N+1); for (int i = 0; i < N-1; ++i) { int u,v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } // precompute pow2 (mod) int MAXP = N + 10; vector pow2(MAXP+1); pow2[0] = 1; for (int i = 1; i <= MAXP; ++i) pow2[i] = (pow2[i-1] * 2) % MOD; // Build parent and order (DFS iterative) vector parent(N+1, -1); vector order; order.reserve(N); stack st; st.push(1); parent[1] = 0; while (!st.empty()) { int u = st.top(); st.pop(); order.push_back(u); for (int v : g[u]) if (parent[v] == -1) { parent[v] = u; st.push(v); } } // down dp vector down(N+1, 0); for (int i = (int)order.size()-1; i >= 0; --i) { int u = order[i]; int best = 0; for (int v : g[u]) if (v != parent[u]) { best = max(best, 1 + down[v]); } down[u] = best; } // up dp vector up(N+1, 0); for (int idx = 0; idx < (int)order.size(); ++idx) { int u = order[idx]; int mx1 = -1, mx2 = -1; for (int v : g[u]) if (v != parent[u]) { int val = 1 + down[v]; if (val > mx1) { mx2 = mx1; mx1 = val; } else if (val > mx2) { mx2 = val; } } for (int v : g[u]) if (v != parent[u]) { int use = mx1; int valv = 1 + down[v]; if (valv == mx1) use = mx2; int cand = up[u]; if (use > cand) cand = use; up[v] = (cand == -1 ? 0 : cand + 1); } } auto modnorm = [&](ll x)->ll{ x %= MOD; if (x < 0) x += MOD; return x; }; // We will keep the best value in two ways: // - best_mod: the value f mod MOD (to output) // - best_big: the exact value f as a big integer (for correct comparison) cpp_int best_big = 0; ll best_mod = 0; bool best_set = false; // For each node r, consider its components and take the top 3 distances x,y,z for (int r = 1; r <= N; ++r) { vector comps; comps.reserve(g[r].size() + 1); comps.push_back(0); if (parent[r] != 0) comps.push_back(up[r]); for (int v : g[r]) if (v != parent[r]) { comps.push_back(1 + down[v]); } if ((int)comps.size() < 3) continue; int a=-1,b=-1,c=-1; for (int v : comps) { if (v > a) { c = b; b = a; a = v; } else if (v > b) { c = b; b = v; } else if (v > c) { c = v; } } int x = a, y = b, z = c; int s = x + y + z; // compute g = 2^{s+3} - (2^{x+2}+2^{y+2}+2^{z+2}) + 6 (exact integer) // then f = g * 2^{N-1-s} // We'll compute exact f as big integer for correct comparison, and also compute f mod MOD to output later. // compute g modulo MOD (for modular f) ll term1 = pow2[s+3]; ll term2 = (pow2[x+2] + pow2[y+2]) % MOD; term2 += pow2[z+2]; term2 %= MOD; ll gmod = modnorm(term1 - term2 + 6); int exp = (N-1) - s; if (exp < 0) continue; // invalid, skip ll fmod = (pow2[exp] * gmod) % MOD; // compute exact f as big integer using cpp_int // g_big = (1 << (s+3)) - (1 << (x+2)) - (1 << (y+2)) - (1 << (z+2)) + 6 cpp_int g_big = cpp_int(1); g_big <<= (s + 3); g_big -= (cpp_int(1) << (x + 2)); g_big -= (cpp_int(1) << (y + 2)); g_big -= (cpp_int(1) << (z + 2)); g_big += 6; if (g_big < 0) continue; // safety, though shouldn't happen cpp_int f_big = g_big << exp; if (!best_set || f_big > best_big) { best_set = true; best_big = f_big; best_mod = fmod; } } cout << (best_mod % MOD) << "\n"; return 0; }