#include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using vi = vector; using vvi = vector; using vvvi = vector; using vll = vector; using vvll = vector; using vvvll = vector; using vmi = vector; using vvmi = vector; using vvvmi = vector; #define all(a) (a).begin(), (a).end() #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) struct RootedTreeLCA { int n; int LOG; vector> g; vector depth; vector par; vector> ch; vector> up; vector tin, tout; int timer; RootedTreeLCA(int n = 0) { init(n); } void init(int n_) { n = n_; g.assign(n, {}); depth.assign(n, 0); par.assign(n, -1); ch.assign(n, {}); tin.assign(n, 0); tout.assign(n, 0); timer = 0; LOG = 1; while ((1 << LOG) <= max(1, n)) LOG++; up.assign(LOG, vector(n, -1)); } void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int root = 0) { fill(par.begin(), par.end(), -1); fill(depth.begin(), depth.end(), 0); for (auto &v : ch) v.clear(); for (auto &row : up) fill(row.begin(), row.end(), -1); timer = 0; vector st; vector it(n, 0); st.reserve(n); st.push_back(root); par[root] = -1; depth[root] = 0; while (!st.empty()) { int v = st.back(); // first visit if (it[v] == 0) { tin[v] = timer++; } if (it[v] == (int)g[v].size()) { tout[v] = timer; st.pop_back(); continue; } int to = g[v][it[v]++]; if (to == par[v]) continue; par[to] = v; depth[to] = depth[v] + 1; ch[v].push_back(to); st.push_back(to); } for (int v = 0; v < n; v++) up[0][v] = par[v]; for (int j = 1; j < LOG; j++) { for (int v = 0; v < n; v++) { int p = up[j - 1][v]; up[j][v] = (p == -1 ? -1 : up[j - 1][p]); } } } // ===== 基本 API ===== int parent(int v) const { return par[v]; } const vector& children(int v) const { return ch[v]; } int get_depth(int v) const { return depth[v]; } vector adj(int v) const { vector res; if (par[v] != -1) res.push_back(par[v]); // parent for (int c : ch[v]) res.push_back(c); // children return res; } // ===== LCA ===== int kth_ancestor(int v, long long k) const { for (int j = 0; j < LOG; j++) { if (v == -1) return -1; if (k & (1LL << j)) v = up[j][v]; } return v; } int lca(int a, int b) const { if (depth[a] < depth[b]) swap(a, b); a = kth_ancestor(a, depth[a] - depth[b]); if (a == b) return a; for (int j = LOG - 1; j >= 0; j--) { if (up[j][a] != up[j][b]) { a = up[j][a]; b = up[j][b]; } } return up[0][a]; } int dist(int a, int b) const { int c = lca(a, b); return depth[a] + depth[b] - 2 * depth[c]; } // start:v, goal:u int jump_on_path(int v, int u, int t) const { int c = lca(v, u); int dv = depth[v] - depth[c]; int du = depth[u] - depth[c]; int d = dv + du; if (t < 0 || t > d) return -1; if (t <= dv) return kth_ancestor(v, t); return kth_ancestor(u, d - t); } int center_node_if_even_dist(int u, int v) const { int d = dist(u, v); if (d & 1) return -1; return jump_on_path(u, v, d / 2); } // is u in subtree of v? bool is_in_subtree(int u, int v) const { return tin[v] <= tin[u] && tin[u] < tout[v]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; set st; rep(i, n)st.insert(i); RootedTreeLCA tr(n); vvi v(n-1, vi(2)); rep(i, n-1){ int a, b; cin >> a >> b; a--; b--; v[i][0] = a; v[i][1] = b; tr.add_edge(a, b); st.erase(b); } int root = *st.begin(); tr.build(root); vmi dp1(n, mint(1)), dp2(n, mint(1)); queue q; vi tmp(n, 0); rep(i, n){ tmp[i] = tr.children(i).size(); if(tmp[i] == 0)q.push(i); } while(!q.empty()){ auto u = q.front(); q.pop(); dp1[tr.parent(u)] += dp1[u]; tmp[tr.parent(u)]--; if(tr.parent(u) == root)continue; if(tmp[tr.parent(u)] == 0)q.push(tr.parent(u)); } q.push(root); while(!q.empty()){ auto u = q.front(); q.pop(); for(auto v : tr.children(u)){ dp2[v] += dp2[u]; q.push(v); } } mint ans = mint(0); rep(i, n-1)ans += dp2[v[i][0]]*(dp1[v[i][1]]); cout << ans.val() << endl; return 0; }