// 比較関数が間違っている場合 #include #include using namespace std; using ll = long long; using pii = pair; using pll = pair; using vi = vector; using vl = vector; #define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c)) #define rep2(i, a, b) rep3(i, a, b, 1) #define rep1(i, n) rep2(i, 0, n) #define rep0(n) rep1(aaaaa, n) #define ov4(a, b, c, d, name, ...) name #define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__) #define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--) #define fore(e, v) for (auto &&e : v) #define all(a) begin(a), end(a) #define sz(a) (int)(size(a)) #define lb(v, x) (lower_bound(all(v), x) - begin(v)) #define eb emplace_back template bool chmin(T &a, const S &b) { return a > b ? a = b, 1 : 0; } template bool chmax(T &a, const S &b) { return a < b ? a = b, 1 : 0; } const int INF = 1e9 + 100; const ll INFL = 3e18 + 100; #define i128 __int128_t struct _ { _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); } } __; using ai3 = array; using ai5 = array; using mint = atcoder::modint998244353; // a bk) return false; if (ak < bk) return true; return a > b; } int main() { ll N; cin >> N; vector G(N); rep(N - 1) { int U, V; cin >> U >> V; --U, --V; G[U].push_back(V); G[V].push_back(U); } unordered_map edge_depth; auto dfs1 = [&](auto f, int v, int p) -> pii { pii ret{0, v}; if (edge_depth.contains(v * N + p)) return edge_depth[v * N + p]; for (int u : G[v]) { if (u != p) chmax(ret, f(f, u, v)); } ret.first++; return edge_depth[v * N + p] = ret; }; dfs1(dfs1, 0, -1); auto dfs2 = [&](auto f, int v, int p) -> void { pii g1{0, v}, g2{-1, v}; for (int u : G[v]) { if (edge_depth.contains(u * N + v)) { pii x = edge_depth[u * N + v]; if (x > g1) { g2 = g1; g1 = x; } else if (x > g2) { g2 = x; } } } g1.first++, g2.first++; for (int u : G[v]) { if (u != p) { if (edge_depth[u * N + v].second == g1.second) { edge_depth[v * N + u] = g2; } else { edge_depth[v * N + u] = g1; } f(f, u, v); } } }; dfs2(dfs2, 0, -1); ai3 ansd{-1, 0, 0}; auto push3 = [](ai3 &x, int v) { if (v > x[0]) { x[2] = x[1], x[1] = x[0], x[0] = v; } else if (v > x[1]) { x[2] = x[1], x[1] = v; } else if (v > x[2]) { x[2] = v; } }; rep(i, N) { ai3 now{0, 0, 0}; for (int u : G[i]) { push3(now, edge_depth[u * N + i].first); // cerr<