#include using namespace std; using ll = long long; const ll MOD = 998244353; 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 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); } } // order currently preorder (root-first). We want postorder for down dp: process reverse 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 (distance from node to farthest outside its subtree) vector up(N+1, 0); // process in preorder (order as we built) for (int idx = 0; idx < (int)order.size(); ++idx) { int u = order[idx]; // find top two among child contributions (1 + down[child]) 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); // up[v] = 1 + max(up[u], best other child) } } auto modnorm = [&](ll x)->ll{ x %= MOD; if (x < 0) x += MOD; return x; }; ll best = 0; // For each node r, collect component farthest distances (from r to farthest node in that neighbor-component) for (int r = 1; r <= N; ++r) { // components: include 0 for choosing r itself // for each child (neighbor != parent) add 1 + down[child] // for parent-component add up[r] (if parent[r] != 0) 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; // find top 3 largest values 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; // distances from r to chosen nodes int s = x + y + z; // compute g = 2^{s+3} - (2^{x+2}+2^{y+2}+2^{z+2}) + 6 // Ensure pow2 indices valid: s+3 <= N+2 etc. We precomputed enough. ll term1 = pow2[s+3]; ll term2 = (pow2[x+2] + pow2[y+2]) % MOD; term2 += pow2[z+2]; term2 %= MOD; ll gval = modnorm(term1 - term2 + 6); // f = 2^{N-1 - s} * gval int exp = (N-1) - s; if (exp < 0) continue; // shouldn't happen for valid triples but safe guard ll fval = (pow2[exp] * gval) % MOD; if (fval > best) best = fval; } cout << best % MOD << "\n"; return 0; }