#include #include using namespace std; using namespace atcoder; using ll = long long; using ld = long double; ll dfs(ll x, ll g, vector> &pass, vector &come){ if(x == g){ come[x] = 0; return 0; } come[x] = 0; for(ll i : pass[x]){ if(come[i] >= 0)continue; ll num = dfs(i,g,pass,come); if(num != -1){ come[x] = num + 1; return come[x]; } } come[x] = -1; return -1; } int main(){ ll n; ll p1,p2; cin >> n; vector> pass(n,vector(0)); ll u,v; for(ll i = 0; i < n-1; i++){ cin >> u >> v; u--; v--; pass[u].push_back(v); pass[v].push_back(u); } queue bfs; vector come1(n,-1); come1[0] = 0; bfs.push(0); pair maxx = {0,0}; while(!bfs.empty()){ ll x = bfs.front(); bfs.pop(); for(ll i : pass[x]){ if(come1[i] >= 0)continue; come1[i] = come1[x] + 1; if(maxx.first < come1[i]){ maxx = {come1[i],i}; } bfs.push(i); } } p1 = maxx.second; maxx = {0,0}; vector come2(n,-1); come2[p1] = 0; bfs.push(p1); while(!bfs.empty()){ ll x = bfs.front(); bfs.pop(); for(ll i : pass[x]){ if(come2[i] >= 0)continue; come2[i] = come2[x] + 1; if(maxx.first < come2[i]){ maxx = {come2[i],i}; } bfs.push(i); } } p2 = maxx.second; ll l = maxx.first; vector come3(n,-1); ll o = dfs(p1,p2,pass,come3); vector come4(n,-1); for(ll i = 0; i < n; i++){ if(come3[i] >= 0){ come3[i] = abs(come3[i]*2 - l); come4[i] = 0; bfs.push(i); } } tuple mm = {0,0,0}; if(l % 2 == 1)get<2>(mm) = 1; else get<2>(mm) = 0; while(!bfs.empty()){ ll x = bfs.front(); bfs.pop(); for(ll i : pass[x]){ if(come4[i] >= 0)continue; come4[i] = come4[x] + 1; come3[i] = come3[x]; if(get<0>(mm) < come4[i]){ mm = {come4[i],i,come3[i]}; }else if(get<0>(mm) == come4[i] && get<2>(mm) > come3[i]){ mm = {come4[i],i,come3[i]}; } bfs.push(i); } } ll a = (l + get<2>(mm))/2; ll b = (l - get<2>(mm))/2; ll c = get<0>(mm); ll d = n-1-a-b-c; vector two(n+1,1); for(ll i = 1; i <= n; i++){ two[i] = (two[i-1] * 2)% 998244353; } ll ans = 998244353 + two[n-1] * 8; ans -= (two[d+1] * ((two[a+1]+two[b+1]+two[c+1] - 3)% 998244353))% 998244353; ans %= 998244353; cout << ans << '\n'; return 0; }