#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define MOD 998244353 #define ld long double #define INF 2251799813685248 #define vall(A) A.begin(),A.end() #define gridinput(vv,H,W) for (ll i = 0; i < H; i++){string T; cin >> T; for(ll j = 0; j < W; j++){vv[i][j] = {T[j]};}} #define adjustedgridinput(vv,H,W) for (ll i = 1; i <= H; i++){string T; cin >> T; for(ll j = 1; j <= W; j++){vv[i][j] = {T[j-1]};}} #define vin(A) for (ll i = 0, sz = A.size(); i < sz; i++){cin >> A[i];} #define vout(A) for(ll i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];} #define adjustedvin(A) for (ll i = 1, sz = A.size(); i < sz; i++){cin >> A[i];} #define adjustedvout(A) for(ll i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];} #define vout2d(A,H,W) for (ll i = 0; i < H; i++){for (ll j = 0; j < W; j++){cout << A[i][j] << " \n"[j==W-1];}} #define encode(i,j) ((i)<<32)+j #define decode(v,w) (w ? (v)%4294967296 : (v)>>32) vector pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296}; vector pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000}; vector di{0,1,0,-1}; vector dj{1,0,-1,0}; /** * @brief ビット(指数)のリストを受け取り、繰り上がり(2^k + 2^k = 2^{k+1}) * を全て処理して正規化された(重複のない)ビットリストを返す。 * * 例: [5, 5, 3] -> [6, 3] * [5, 5, 6] -> [7] * * @param bits ビット(指数)のリスト。 * Pythonと異なり、この関数内でソートするために * 値渡し(コピー)で受け取ります。 * @return std::vector 正規化されたビットのリスト。 */ std::vector normalize_bits(std::vector bits) { if (bits.empty()) { return {}; // 空のベクターを返す } // bits_sorted = sorted(bits, reverse=True) // 入力ベクター(のコピー)を降順にソート std::sort(bits.begin(), bits.end(), std::greater()); std::vector stack; // for b in bits_sorted: for (ll b : bits) { // while len(stack) > 0 and stack[-1] == b: while (!stack.empty() && stack.back() == b) { // b = stack.pop() + 1 b = stack.back() + 1; stack.pop_back(); // Pythonの .pop() に相当 } // stack.append(b) stack.push_back(b); } return stack; } /** * @brief 非負整数の3つ組 (a,b,c) と (d,e,f) を受け取り、 * F(a,b,c) = (2^{a+1}+2^{b+1}+2^{c+1}-3) / 2^{a+b+c} * F(d,e,f) = (2^{d+1}+2^{e+1}+2^{f+1}-3) / 2^{d+e+f} * の大小を比較する。 * * @param abc (a, b, c) を含むベクター * @param def (d, e, f) を含むベクター * @return int * 1 : F(a,b,c) > F(d,e,f) * 0 : F(a,b,c) == F(d,e,f) * -1 : F(a,b,c) < F(d,e,f) */ int compare_fractions(const std::vector& abc, const std::vector& def) { // a, b, c = abc ll a = abc[0]; ll b = abc[1]; ll c = abc[2]; // d, e, f = def_ ll d = def[0]; ll e = def[1]; ll f = def[2]; // A = a + b + c // C++17以降の場合: // ll A = std::reduce(abc.begin(), abc.end()); // ll D = std::reduce(def.begin(), def.end()); // C++11互換: ll A = a + b + c; ll D = d + e + f; // 方針2で導出した両辺の指数リストを作成 std::vector lhs_bits = { a + 1 + D, b + 1 + D, c + 1 + D, A + 1, A }; std::vector rhs_bits = { d + 1 + A, e + 1 + A, f + 1 + A, D + 1, D }; // 方針3: ビットリストを正規化 std::vector norm_lhs = normalize_bits(lhs_bits); std::vector norm_rhs = normalize_bits(rhs_bits); // 方針4: 正規化済みリストを辞書順に比較 // std::vector の比較演算子は辞書順比較をサポートしています。 if (norm_lhs < norm_rhs) { return 1; } else { return 0; } } /// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。 /// @param a /// @param b /// @param m /// @return a^b%m ll modpow(ll a, ll b, ll m){ ll t = a; ll ans = 1; while (b > 0){ if (b%2){ ans = (ans*t)%m; } b /= 2; t = (t*t)%m; } return ans; } void dfs(vector> &E, vector &D, ll now){ for (auto v : E[now]){ if (D[v] != -1){ continue; } D[v] = D[now]+1; dfs(E,D,v); } } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); ll N; cin >> N; vector> E(N+1); for (ll i = 0; i < N-1; i++){ ll u,v; cin >> u >> v; E[u].push_back(v); E[v].push_back(u); } vector D(N+1,-1); vector D2(N+1,-1); vector D3(N+1,-1); D[1] = 0; dfs(E,D,1); ll dist_max_v = -1; ll d_max = -1; for (ll i = 1; i <= N; i++){ if (D[i] >= d_max){ d_max = D[i]; dist_max_v = i; } } D2[dist_max_v] = 0; dfs(E,D2,dist_max_v); ll dist_max_v2 = -1; d_max = -1; for (ll i = 1; i <= N; i++){ if (D2[i] >= d_max){ d_max = D2[i]; dist_max_v2 = i; } } D3[dist_max_v2] = 0; dfs(E,D3,dist_max_v2); ll diameter = D2[dist_max_v2]; vector> ans; for (ll i = 1; i <= N; i++){ if (i == dist_max_v || i == dist_max_v2){continue;} ll l = D2[i] + D3[i] - diameter; l /= 2; ll k = D3[i]-l; ll m = D2[i]-l; ll answer = modpow(2,N+2,MOD) - modpow(2,N-k-l-m,MOD)*((2*(modpow(2,k,MOD) + modpow(2,l,MOD) + modpow(2,m,MOD))-3)%MOD); answer %= MOD; answer += MOD; answer %= MOD; vector temp{k,l,m, answer}; ans.push_back(temp); } sort(vall(ans),[](const vector &a, const vector &b){return !compare_fractions({a[0],a[1],a[2]}, {b[0],b[1],b[2]});}); cout << ans.back().back() << "\n"; }