""" Gemini Tree Ver.lapis (4) 想定WA解3 切り方が1通りの時の条件ミス """ import sys from sys import stdin mod = 998244353 from collections import deque # startからBFS. 距離、親、訪問順を返す def NC_Dij(lis,start): ret = [float("inf")] * len(lis) ret[start] = 0 visit = [] q = deque([start]) plis = [i for i in range(len(lis))] while len(q) > 0: now = q.popleft() visit.append(now) for nex in lis[now]: if ret[nex] > ret[now] + 1: ret[nex] = ret[now] + 1 plis[nex] = now q.append(nex) return ret,plis,visit def modfac(n, MOD): f = 1 factorials = [1] for m in range(1, n + 1): f *= m f %= MOD factorials.append(f) inv = pow(f, MOD - 2, MOD) invs = [1] * (n + 1) invs[n] = inv for m in range(n, 1, -1): inv *= m inv %= MOD invs[m - 1] = inv return factorials, invs def modnCr(n,r): if n < 0 or r < 0 or n < r: return 0 return fac[n] * inv[n-r] * inv[r] % mod fac,inv = modfac(200000,mod) N = int(stdin.readline()) # 制約チェック assert 1 <= N <= 10**5 lis = [ [] for i in range(N) ] for i in range(N-1): u,v = map(int,stdin.readline().split()) u -= 1 v -= 1 lis[u].append(v) lis[v].append(u) # サイズ X の部分木を切り取る方法は何通りあるか? 切り取れる場合、含む葉の個数の最小は? # を計算する _,plis,visit = NC_Dij(lis,0) chnode = [1] * N # 子部分木のサイズ chleaf = [0] * N # 頂点の子部分木の葉の個数 leaf_num = 0 #葉の全体の個数 for i in range(N): if len(lis[i]) == 1: leaf_num += 1 chleaf[i] += 1 for v in reversed(visit): if plis[v] != v: chnode[plis[v]] += chnode[v] chleaf[plis[v]] += chleaf[v] cut_case_num = [0] * (N+1) #サイズXの部分木を切り取る方法は何通りあるか? cut_v = [ None for i in range(N+1) ] #サイズXの部分木を切り取る際のX側の頂点 cut_leaf_min = [float("inf")] * (N+1) #サイズXの部分木を切り取る時、葉の最小個数は? for v in range(N): cut_case_num[chnode[v]] += 1 cut_leaf_min[chnode[v]] = min(cut_leaf_min[chnode[v]] , chleaf[v]) cut_v[chnode[v]] = v cut_case_num[N-chnode[v]] += 1 cut_leaf_min[N-chnode[v]] = min(cut_leaf_min[N-chnode[v]] , leaf_num-chleaf[v]) cut_v[N-chnode[v]] = plis[v] # ここから実際の処理 # G < B を探索 ans = 0 for G in range(N+1): B = N-G if G > B: break elif G == B: if cut_case_num[G] > 0: ans += modnCr(N,G) ans %= mod else: ans += 0 break elif G == 0: #G=0 or B=0 の場合, コーナーとして処理 ans += 2 continue # G < B の場合 if cut_case_num[G] == 0: ans += 0 elif cut_case_num[G] >= 2: ans += 2 * modnCr(N,G) ans %= mod else: # 1通りしか切り方がない場合 leafG = cut_leaf_min[G] leafB = cut_leaf_min[B] # サイズG側の葉に少なくとも1つの緑 or サイズB側の葉に少なくとも1つの青 がある場合 gb_not_eq = 0 # 満たさない場合 if leafG <= B and leafB <= G: gb_not_eq = modnCr(N-leaf_num,B-leafG) ans += 2 * (modnCr(N,G) - gb_not_eq) ans %= mod # 残った gb_not_eq の割当 flag = False # 部分木g側にある青い葉を消す場合→ b側からB-1を取れるか? if len(lis[cut_v[B]]) <= 2: flag = True # 部分木b側にある緑の葉を消す場合→ g側からg-1を取れるか? if len(lis[cut_v[G]]) <= 2: flag = True # 部分木b側にある緑の葉を消す場合→ B側からg-1を取れるか? if cut_case_num[G-1] > 0 and cut_leaf_min[G-1] < cut_leaf_min[B]: #flag = True pass if flag: ans += 2 * gb_not_eq ans %= mod print (ans % mod)