#include #include using namespace std; using isize = size_t; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using f64 = long double; using p2 = pair; using el = tuple; using mint = atcoder::modint998244353; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(18); _main(); } i64 pow(i64 x, i64 n) { i64 res = 1; i64 t = x; while (n > 0) { if (n & 1) { res = res * t; } t = t * t; n >>= 1; } return res; } i64 pow(i64 x, i64 n, i64 m) { i64 res = 1; i64 t = x % m; while (n > 0) { if (n & 1) { res = res * t % m; } t = t * t % m; n >>= 1; } return res; } vector g[100000]; vector dp[100000]; void merge(vector &dp, p2 v) { dp.push_back(v); sort(dp.begin(), dp.end()); reverse(dp.begin(), dp.end()); set st; vector ndp; for (auto [x, i] : dp) { if (st.count(i)) continue; ndp.push_back({x, i}); st.insert(i); } while (ndp.size() > 3) ndp.pop_back(); dp = ndp; } void dfs(i64 v, i64 par) { for (i64 nv : g[v]) { if (nv == par) continue; dfs(nv, v); if (!dp[nv].empty()) merge(dp[v], {dp[nv][0].first + 1, nv}); } } void dfs1(i64 v, i64 par, i64 np) { if (np >= 0) merge(dp[v], {np, par}); for (i64 nv : g[v]) { if (nv == par) continue; i64 mx = -1; for (auto [x, i] : dp[v]) if (i != nv) mx = max(mx, x + 1); dfs1(nv, v, mx); } } void _main() { i64 n; cin >> n; for (i64 i = 0; i < n - 1; i++) { i64 u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } for (i64 i = 0; i < n; i++) { for (i64 j = -3; j <= -1; j++) { merge(dp[i], {0, j}); } } dfs(0, -1); dfs1(0, -1, -1); vector> v; auto add = [](set &st, i64 x) { while (st.count({x, x + 1})) { st.erase({x, x + 1}); x++; } st.insert({x, x + 1}); }; auto del = [](set &st, i64 x) { auto it = st.lower_bound((p2){x + 1, 0}); if (it == st.begin() || prev(it)->second <= x) { auto [l, r] = *it; st.erase({l, r}); assert(x < l); st.insert({x, x + 1}); if (x + 1 < l) st.insert({x + 1, l}); if (l + 1 < r) st.insert({l + 1, r}); } else { auto [l, r] = *prev(it); st.erase({l, r}); if (l < x) st.insert({l, x}); if (x + 1 < r) st.insert({x + 1, r}); } }; for (i64 i = 0; i < n; i++) { i64 a = dp[i][0].first; i64 b = dp[i][1].first; i64 c = dp[i][2].first; i64 d = n - 1 - a - b - c; set st; add(st, a + d + 2), add(st, b + d + 2), add(st, c + d + 2); del(st, d + 1), del(st, d + 2); v.push_back(st); } sort(v.begin(), v.end(), [](set x, set y){ while (!x.empty() && !y.empty()) { auto [l, r] = *prev(x.end()); auto [ll, rr] = *prev(y.end()); if (r != rr) { return r < rr; } x.erase({l, r}), y.erase({ll, rr}); i64 p = max(l, ll); if (l < p) x.insert({l, p}); if (ll < p) y.insert({ll, p}); } if (x.empty()) return true; else return false; }); mint ans = 0; set st = v[0]; for (auto [a, b] : st) { for (i64 i = a; i < b; i++) { ans += mint(2).pow(i); } } ans = mint(2).pow(n + 2) - ans; cout << ans.val() << "\n"; }