#include #include using namespace std; using ll = long long; const ll MOD = 998244353; using boost::multiprecision::cpp_int; // 意図的に非効率な O(N^2) に近い(最悪ノード訪問が O(N^2) になる) // 「各頂点 r に対して、その隣接成分ごとに DFS を行って最遠距離を求める」 // という愚直実装。 // 正しさは保ちつつ計算量を落とさない(意図的)実装例。 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); } // 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; auto modnorm = [&](ll x)->ll{ x %= MOD; if (x < 0) x += MOD; return x; }; // 最良解を保持(大きさ比較用に任意精度整数、出力は mod) cpp_int best_big = 0; ll best_mod = 0; bool best_set = false; // タイムスタンプ法で visited を管理(各 DFS ごとに初期化を避ける) vector seen(N+1, 0); int cur_time = 1; // 各頂点 r を会合点として愚直に調べる for (int r = 1; r <= N; ++r) { vector comps; // r から見た各成分の距離(0 を含める) comps.reserve(g[r].size() + 1); comps.push_back(0); // r 自身を選ぶ候補 // 各隣接成分ごとに DFS をして r からの最遠距離を求める for (int v : g[r]) { // DFS starting at v, but never visit r int maxd = 0; ++cur_time; // mark r as seen for this DFS to block going back seen[r] = cur_time; // iterative stack (node, depth) stack> st; st.push({v, 1}); seen[v] = cur_time; while (!st.empty()) { auto [u, d] = st.top(); st.pop(); if (d > maxd) maxd = d; for (int w : g[u]) { if (seen[w] != cur_time) { seen[w] = cur_time; st.push({w, d+1}); } } } comps.push_back(maxd); } if ((int)comps.size() < 3) continue; // 3つ取れないならスキップ // 上位3つを取る(降順ソートして先頭3つ) sort(comps.begin(), comps.end(), greater()); int x = comps[0], y = comps[1], z = comps[2]; int s = x + y + z; int exp = (N - 1) - s; if (exp < 0) continue; // 無効な選択(理論上ありえないかもしれないが安全対策) // g mod と f mod 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); ll fmod = (pow2[exp] * gmod) % MOD; // 正確な比較のために任意精度整数でも f を計算 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; // 安全対策 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; }