# 答えを陽に持つ from collections import deque from collections import Counter 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) # =================================== MOD = 998244353 N = int(input()) 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) top3_array = [TopK(3, 0) for _ in range(N)] # ある頂点から見た部分木の中で深さtop3のやつ # 子から親への頂点を削除 O(M) 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) # print(connect) # print(parents) # print(tps) # 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 # print(res_BU) # print([x.array for x in top3_array]) # Top-Down DP acc_TD = [0] * N res_TD = [0] * N res = [0]*N # 1. 初期化の修正 res_TD[0] = 0 # 根の「親側」の深さは0 res[0] = max(res_BU[0], res_TD[0]) # 根の最大深さ top3_array[0].add(res_TD[0]) # 根のtop3にも親側(0)を追加 for i in tps: # 2. array の構築を修正 # 子のBU深さリスト + 親側(TD)の深さ array = [res_BU[c] for c in connect[i]] array.append(res_TD[i]) # res[parents[i]] ではなく res_TD[i] # print("Debug",i,parents[i],array) # デバッグ用 L = len(array) # 右向き累積max (左からi-1番目までのmax) accr_cum = [-float("inf")]*(len(array)+1) for j, v in enumerate(array): accr_cum[j+1] = max(accr_cum[j], v) # 左向き累積max (右からi+1番目までのmax) 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]) # print(accr_cum, accl_cum) # デバッグ用 # 3. acc_TD, res_TD の更新ロジックを修正 for j, c in enumerate(connect[i]): # c 以外の方向の最大深さを計算 # (arrayのj番目が c のBU深さ だった) acc_TD_for_c = max(accr_cum[j], accl_cum[j+1]) # c にとっての「親側(i)からの深さ」は acc_TD_for_c + 1 res_TD[c] = acc_TD_for_c + 1 # c の最大深さ(偏心度)を更新 res[c] = max(res_BU[c], res_TD[c]) # c のtop3に「親側からの深さ」を追加 top3_array[c].add(res_TD[c]) # print("add",j,c,res[c],top3_array[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) ans = 0 for i in range(N): x = f(top3_array[i].array) if ans < x: ans = x print(ans % 998244353)