class TopK: def __init__(self,K,e): self.array = [e]*K self._index = 0 self.K = K self.e = e def add(self,x): for i in range(self.K): if x >= self.array[i]: self.array = self.array[:i] + [x] + self.array[i:-1] break def __str__(self): return str(self.array) from collections import Counter def normalize_bits(bits): """ ビット(指数)のリストを受け取り、繰り上がり(2^k + 2^k = 2^{k+1}) を全て処理して正規化された(重複のない)ビットリストを返す。 例: [5, 5, 3] -> [6, 3] [5, 5, 6] -> [7] """ if not bits: return [] bits_sorted = sorted(bits,reverse=True) stack = [] for i in range(len(bits_sorted)): b = bits_sorted[i] while len(stack) > 0 and stack[-1] == b: b = stack.pop()+1 stack.append(b) #print(stack) return stack def compare_fractions(abc, def_): """ 非負整数の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} の大小を比較する。 戻り値: - 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) """ a, b, c = abc d, e, f = def_ A = a + b + c D = d + e + f # 方針2で導出した両辺の指数リストを作成 lhs_bits = [ a + 1 + D, b + 1 + D, c + 1 + D, A + 1, A ] rhs_bits = [ d + 1 + A, e + 1 + A, f + 1 + A, D + 1, D ] # 方針3: ビットリストを正規化 norm_lhs = normalize_bits(lhs_bits) norm_rhs = normalize_bits(rhs_bits) # 方針4: 正規化済みリストを辞書順に比較 if norm_lhs > norm_rhs: return 1 elif norm_lhs < norm_rhs: return -1 else: return 0 # =================================== from collections import deque MOD = 998244353 N = int(input()) degrees = [0]*N connect = [[] for _ in range(N)] for _ in range(N-1): u,v = map(lambda x:int(x)-1,input().split()) connect[u].append(v) connect[v].append(u) degrees[u] += 1 degrees[v] += 1 top3_array = [TopK(3,0) for _ in range(N)] parents = [-1] * N tps = [] Q = deque([0]) while Q: i = Q.popleft() tps.append(i) for a in connect[i]: if a != parents[i]: parents[a] = i connect[a].remove(i) Q.append(a) # Bottom-Up DP acc_BU = [0] * N res_BU = [0] * N for i in tps[1:][::-1]: res_BU[i] = acc_BU[i] + 1 p = parents[i] acc_BU[p] = max(acc_BU[p], res_BU[i]) top3_array[p].add(res_BU[i]) res_BU[tps[0]] = acc_BU[tps[0]] + 1 acc_TD = [0] * N res_TD = [0] * N res = [0]*N res_TD[0] = 0 res[0] = max(res_BU[0], res_TD[0]) top3_array[0].add(res_TD[0]) for i in tps: array = [res_BU[c] for c in connect[i]] array.append(res_TD[i]) L = len(array) accr_cum = [-float("inf")]*(len(array)+1) for j,v in enumerate(array): accr_cum[j+1] = max(accr_cum[j],v) accl_cum = [-float("inf")]*(len(array)+1) for j,v in enumerate(reversed(array)): accl_cum[L-j-1] = max(v,accl_cum[L-j]) for j,c in enumerate(connect[i]): acc_TD_for_c = max(accr_cum[j], accl_cum[j+1]) res_TD[c] = acc_TD_for_c + 1 res[c] = max(res_BU[c], res_TD[c]) top3_array[c].add(res_TD[c]) def f(t): a,b,c = t K = a+b+c return 2**(N+2) - 2**(N-K)*(2**(a+1) + 2**(b+1) + 2**(c+1) - 3) M = [0,0,0] for i in range(N): x = top3_array[i].array #print(f(x),f(M),compare_fractions(x,M)) if degrees[i] >= 2 and compare_fractions(M,x) == 1: M = x a,b,c = M K = sum(M) #print(a,b,c) ans = pow(2,N+2,MOD) - pow(2,N-K,MOD) * (pow(2,a+1,MOD) + pow(2,b+1,MOD) + pow(2,c+1,MOD) - 3) ans %= MOD print(ans)