# pragma GCC target("avx2") # pragma GCC optimize("O3") # pragma GCC optimize("unroll-loops") #include #include // cout, endl, cin #include // string, to_string, stoi #include // vector #include // min, max, swap, sort, reverse, lower_bound, upper_bound #include // pair, make_pair #include // tuple, make_tuple #include // int64_t, int*_t #include // printf #include // map #include // queue, priority_queue #include // set #include // stack #include // deque #include // unordered_map #include // unordered_set #include // bitset #include // isupper, islower, isdigit, toupper, tolower #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define endl '\n' #define all(x) (x).begin(),(x).end() #define arr(x) (x).rbegin(),(x).rend() typedef long long ll; typedef unsigned long long ull; const ll inf=4e18; using graph = vector > ; using vi=vector; using P= pair; using pii=pair; using pll=pair; using vvi=vector; using vvvi=vector; using vll=vector; using vvll=vector; using vvvll=vector; using vp=vector

; using vvp=vector; using vvvp=vector; using vd=vector; using vvd =vector; //using vs=vector; //string T="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //string S="abcdefghijklmnopqrstuvwxyz"; //g++ main.cpp -std=c++17 -I . //cout < bool chmin(T& a, T b) { if (a > b) { a = b; return true; } else return false; } template bool chmax(T& a, T b) { if (a < b) { a = b; return true; } else return false; } struct edge{ int to; ll cost;int id; edge(int to,ll cost,int id) : to(to),cost(cost),id(id) {} }; using ve=vector; using vve=vector; int mod=998244353; using mint=modint998244353; using vm=vector; using vvm=vector; using vvvm=vector; constexpr int MAX = 10; ll fact[MAX],finv[MAX],invv[MAX]; void initcomb(){ fact[0]=fact[1]=1; finv[0]=finv[1]=1; invv[1]=1; for(int i=2;i par, siz; UnionFind(int n) : par(n, -1) , siz(n, 1) { } int root(int x) { if (par[x] == -1) return x; else return par[x] = root(par[x]); } bool issame(int x, int y) { return root(x) == root(y); } bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; return true; } int size(int x) { return siz[root(x)]; } }; vll anss; void solve(int test){ int n; cin >> n; vve g(n); rep(i,n-1){ int a,b; cin >> a >> b; a--;b--; g[a].push_back(edge(b,1,i)); g[b].push_back(edge(a,1,i)); } vll dp(n,-inf); { auto dfs=[&](auto dfs,int v,int p=-1)->void { chmax(dp[v],0ll); for(auto u:g[v]){ if(u.to==p)continue; dfs(dfs,u.to,v); chmax(dp[v],dp[u.to]+1); } }; dfs(dfs,0,-1); } vll dp2(n,-inf); { auto dfs=[&](auto dfs,int v,int p=-1)->void { set

st; for(auto u:g[v]){ if(u.to==p)continue; chmax(dp2[u.to],dp2[v]+1); st.insert(P(dp[u.to],u.to)); } if(st.size()>=2){ /* if(v==0){ cout << "test" << endl; auto it=st.begin(); while(it!=st.end()){ cout << it->first << " " << it->second << endl; it++; } } */ for(auto u:g[v]){ if(u.to==p)continue; auto it=st.lower_bound(P(dp[u.to],u.to)); st.erase(*it); auto itb=st.rbegin(); chmax(dp2[u.to],itb->first+2); /* if(v==0){ cout <<"te "<< u.to+1 << " " << (itb->first+2) << endl; } */ st.insert(P(dp[u.to],u.to)); } } for(auto u:g[v]){ if(u.to==p)continue; dfs(dfs,u.to,v); } }; dp2[0]=0; dfs(dfs,0,-1); } /* rep(v,n){ cout << dp[v] << " " << dp2[v] << endl; } */ vll ansv={-1,-1,-1}; { vll dam={-1,-1,-1}; vll maxv={-1,-1,-1}; auto dfs=[&](auto dfs,int v,int p=-1)->void { vll vs; for(auto u:g[v]){ if(u.to==p)continue; dfs(dfs,u.to,v); vs.push_back(dp[u.to]+1); } vs.push_back(dp2[v]); while(vs.size()<3)vs.push_back(0); sort(arr(vs)); rep(i,3)dam[i]=vs[i]; reverse(all(dam)); vll damdam={dam[0]+dam[1],dam[1]+dam[2],dam[2]+dam[0]}; sort(all(damdam)); if(chmax(maxv,damdam)){ ansv=dam; } /* if(chmax(ansv,dam)){ cout << v+1 << endl; rep(i,3)cout << dam[i] << " "; cout << endl; } cout << v+1 << endl; for(auto val:vs)cout << val << " "; cout << endl; rep(i,3)cout << dam[i] << " "; cout << endl; */ }; dfs(dfs,0,-1); } // rep(v,n)cout << v+1 << " " << dp[v] << " " << dp2[v] << endl; mint ans=0; { int da=ansv[0]; int db=ansv[1]; int dc=ansv[2]; ans+=mint(2).pow(da+1); ans+=mint(2).pow(db+1); ans+=mint(2).pow(dc+1); ans-=3; ans*=mint(2).pow(n-da-db-dc); ans=mint(2).pow(n+2)-ans; //cout <>t; rep(test,t)solve(test); for(auto ans:anss){ cout<< ans << endl; } }