#include using namespace std; #define ll long long #define rep(i,n) for(int i=0;i #define Tp tuple #define all(v) v.begin(),v.end() #define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr);typedef modint mint using Graph = vector>; const ll mod = 998244353; template struct modint{ uint64_t val; constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){} constexpr modint operator-() const noexcept{ return modint(*this)=mod-val; } constexpr modint operator+(const modint rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint operator-(const modint rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint operator*(const modint rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint operator/(const modint rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint &operator+=(const modint rhs) noexcept{ val+=rhs.val; val-=((val>=mod)?mod:0); return (*this); } constexpr modint &operator-=(const modint rhs) noexcept{ val+=((val>=1; } return (*this)*=now; } constexpr bool operator==(const modint rhs) noexcept{ return val==rhs.val; } constexpr bool operator!=(const modint rhs) noexcept{ return val!=rhs.val; } friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{ return os<<(x.val); } friend constexpr istream &operator>>(istream& is,modint& x) noexcept{ uint64_t t; is>>t,x=t; return is; } }; //segment tree //1-indexed all class segtree { public: ll n; vector A; segtree(ll k){ n = 1; while(n(2*n,0); } //a[i]にxを加算する void add(ll i,ll x){ int index = n-1+i; A[index] += x; while(index>1){ index /= 2; A[index] = max(A[2*index],A[2*index+1]); } } //a[i]をにする void replace(ll i,ll x){ int index = n-1+i; A[index] = x; while(index>1){ index /= 2; A[index] = max(A[2*index],A[2*index+1]); } } //a[i]+a[i+1]+…+a[j]を求める ll mx(ll i,ll j){ return rangesum(i,j,1,1,n); } // a,b求める区間 k区間番号 c,d区間の始終点(k=1,c=1,d=nで入力する) ll rangesum(ll a,ll b,ll k,ll c,ll d){ //単位元の設定 ll el = 0; if(d vis; int t; vector euler_time; void dfs(Graph &G, int s,int i){ t++; ll st = t; for(int nx:G[s]){ if(vis[nx]==i) continue; vis[nx] = i; dfs(G,nx,i); } t++; ll en = t; euler_time[s] = make_pair(st,en); } void dfs_dp(Graph &G, int s,int i){ for(int nx:G[s]){ if(vis[nx]==i) continue; vis[nx] = i; dfs_dp(G,nx,i); } auto[st,en] = euler_time[s]; ll m1 = seq.mx(st,en); ll m1_val = m1/base; ll m1_idx = m1%base; seq.replace(m1_idx,0); ll m2 = seq.mx(st,en); ll m2_val = m2/base; ll m2_idx = m2%base; seq.replace(m2_idx,0); // cout << "----------" << endl; // cout << m1_val << " " << m2_val << endl; if(m1_val%2==0&&m2_val>0&&m2_val%2==0){ m2_val--; //cout << m2_val << endl; seq.replace(m2_idx,base+m2_idx); } seq.replace(st,(m1_val+m2_val+1)*base+st); //cout << s << " " << (m1_val+m2_val+1) << endl; } int main() { riano_; ll ans = 0; ll N; cin >> N; Graph G(N+1); rep(i,N-1){ ll a,b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } //main関数内で vis.assign(N+1,-1); euler_time.assign(N+1,make_pair(0,0)); int s = 1; vis[s] = 0; t = 0; //s:始点 dfs(G,s,0); //s:始点 vis[s] = 1; dfs_dp(G,s,1); ans = seq.mx(1,2*N)/base; cout << ans << endl; }