#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i, s, e) for (int i = int(s); i < int(e); ++i) #define RFOR(i, s, e) for (int i = int(e) - 1; i >= int(s); --i) #define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i) #define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i) #define ALL(x) (x).begin(),(x).end() #define rep(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i) #define rrep(i, n) for (int i = int(n) - 1; i >= 0; --i) #define all(x) (x).begin(),(x).end() template inline void chmin(T& a, T b) { if (b < a) { a = b; } } template inline void chmax(T& a, T b) { if (a < b) { a = b; } } template inline constexpr T square(T v) { return v * v; } template void InstanceRun(Params&&... params) { T* m = new T; m->Run(forward(params)...); } struct Main; int main(int argc, const char* argv[]) { cin.tie(0); ios::sync_with_stdio(0); InstanceRun
(argc, argv); } using ll = long long; #define int ll #define INF INT64_MAX template struct arr : public vector { static arr> D2(int y, int x, T value) { return arr>(y, arr(x, value)); } static arr>> D3(int z, int y, int x, T value) { return arr>>(z, arr>(y, arr(x, value))); } static arr Iota(int N, int value = 0) { auto r = arr(N); r.iota(value); return r; } arr() {} arr(initializer_list il) : vector(il) {} explicit arr(int n) : vector(n) {} arr(int n, T v) : vector(n, v) {} arr(const arr& r) : vector(r) {} arr(arr&& r) : vector(move(r)) {} arr& operator = (const arr& r) { vector::operator = (r); return *this; } arr& operator = (arr&& r) { vector::operator = (move(r)); return *this; } T& operator()(int i) { return (*this)[i]; } T const& operator()(int i) const { return (*this)[i]; } void init(int n, T v = T()) { this->assign(n, v); } int sz() const { return (int)this->size(); } void pb(T v) { this->push_back(v); } void sort() { std::sort(this->begin(), this->end()); } template void sort(F&& f) { std::sort(this->begin(), this->end(), f); } void rsort() { std::sort(this->begin(), this->end(), greater()); } void reverse() { std::reverse(this->begin(), this->end()); } void unique_erase() { this->erase(std::unique(this->begin(), this->end()), this->end()); } bool next_permutation() { return std::next_permutation(this->begin(), this->end()); } int lower_bound(T const& v, function p) { return std::lower_bound(this->begin(), this->end(), v, p) - this->begin(); } int lower_bound(T const& v) { return std::lower_bound(this->begin(), this->end(), v) - this->begin(); } int upper_bound(T const& v, function p) { return std::upper_bound(this->begin(), this->end(), v, p) - this->begin(); } int upper_bound(T const& v) { return std::upper_bound(this->begin(), this->end(), v) - this->begin(); } void iota(T startValue = 0) { ::iota(this->begin(), this->end(), startValue); } void fill(T v) { ::fill(this->begin(), this->end(), v); } int find_sorted_nearest(T const& v) { int i = this->lower_bound(v); if (i >= sz()) { --i; } else if ((*this)[i] != v) { int p = i - 1; if (p >= 0) { int id = abs((*this)[i] - v); int pd = abs((*this)[p] - v); if (pd < id) { i = p; } } } return i; } int find_sorted(T const& v) { int i = this->lower_bound(v); if (i >= sz()) { return -1; } if ((*this)[i] != v) { return -1; } return i; } int find(T const& v) const { auto it = std::find(this->begin(), this->end(), v); if (it == this->end()) { return -1; } return (int)(it - this->begin()); } bool is_contains(T const& v) const { auto it = std::find(this->begin(), this->end(), v); if (it == this->end()) { return false; } return true; } template void remove_if_erase(P&& predicate) { this->erase(std::remove_if(this->begin(), this->end(), predicate), this->end()); } T& emplace_back_ref() { this->emplace_back(); return this->back(); } friend ostream& operator<<(ostream& os, const arr& p) { if (p.empty()) { return os; } os << p[0]; FOR(i, 1, p.size()) { os << " " << p[i]; } return os; } }; using ints = arr; template struct pr { union { A a; A key; A first; A x; }; union { B b; B value; B second; B y; }; bool operator == (pr const& r) const { return a == r.a && b == r.b; } bool operator != (pr const& r) const { return !((*this) == r); } bool operator < (pr const& r) const { if (a == r.a) { return b < r.b; } return a < r.a; } pr& operator += (pr const& v) { a += v.a; b += v.b; return *this; } pr& operator -= (pr const& v) { a -= v.a; b -= v.b; return *this; } pr operator + (pr const& v) const { return pr{ a, b } += v; } pr operator - (pr const& v) const { return pr{ a, b } -= v; } pr operator - () const { return pr{ -a, -b }; } template operator pr() const { return { C(a), D(b) }; } template auto operator * (T const& v) const -> pr { return { x * v, y * v }; } template auto operator / (T const& v) const -> pr { return { x / v, y / v }; } template pr& operator *= (T const& v) { x *= v; y *= v; return *this; } template pr& operator /= (T const& v) { x /= v; y /= v; return *this; } void flip() { swap(x, y); } friend istream& operator>>(istream& is, pr& p) { is >> p.a >> p.b; return is; } friend ostream& operator<<(ostream& os, pr const& p) { os << p.a << " " << p.b; return os; } }; using pint = pr; using pdouble = pr; static_assert(is_pod::value, "not pod"); template struct tr { union { A a; A first; A x; }; union { B b; B second; B y; }; union { C c; C third; C z; }; bool operator == (tr const& r) const { return a == r.a && b == r.b && c == r.c; } bool operator != (tr const& r) const { return !((*this) == r); } bool operator < (tr const& r) const { if (a == r.a) { if (b == r.b) { return c < r.c; } return b < r.b; } return a < r.a; } tr operator + (tr v) const { return tr(x, y, z) += v; } tr operator - (tr v) const { return tr(x, y, z) -= v; } tr operator - () const { return tr{ -x, -y, -z }; } tr& operator += (tr v) { x += v.x; y += v.y; z += v.z; return *this; } tr& operator -= (tr v) { x -= v.x; y -= v.y; z -= v.z; return *this; } friend istream& operator>>(istream& is, tr& p) { is >> p.a >> p.b >> p.c; return is; } friend ostream& operator<<(ostream& os, tr const& p) { os << p.a << " " << p.b << " " << p.c; return os; } }; using tint = tr; static_assert(is_pod::value, "not pod"); template struct arr2 { vector> m_vec; int m_width; int m_height; arr2() : m_width(0), m_height(0) {} arr2(int w, int h, T const& value = T()) : m_width(w), m_height(h) { m_vec.resize(h, vector(w, value)); } arr2(arr2 const& r) { m_vec = r.m_vec; m_width = r.m_width; m_height = r.m_height; } arr2(arr2&& r) { m_vec = move(r.m_vec); m_width = r.m_width; m_height = r.m_height; } arr2& operator=(arr2 const& r) { m_vec = r.m_vec; m_width = r.m_width; m_height = r.m_height; return *this; } arr2& operator=(arr2&& r) { m_vec = move(r.m_vec); m_width = r.m_width; m_height = r.m_height; return *this; } bool operator ==(arr2 const& r) const { return m_vec == r.m_vec; } bool operator <(arr2 const& r) const { if (m_width != r.m_width) { return m_width < r.m_width; } if (m_height != r.m_height) { return m_height < r.m_height; } REP(y, m_height) { REP(x, m_width) { if ((*this)(x, y) != r(x, y)) { return (*this)(x, y) < r(x, y); } } } return false; } pint size() const { return pint{ m_width, m_height }; } int width() const { return m_width; } int height() const { return m_height; } void clear() { m_vec.clear(); m_width = 0; m_height = 0; } void init(int w, int h, T const& value = T()) { m_vec.clear(); m_vec.resize(h, vector(w, value)); m_width = w; m_height = h; } void init(pint size, T const& value = T()) { init(size.x, size.y, value); } #if VALIDATION void CheckOutOfRange(int x, int y) const { if (x < 0 || y < 0 || x >= m_width || y >= m_height) { VALIDATE_ABORT(); } } void CheckOutOfRange(const pint& p) const { if (p.x < 0 || p.y < 0 || p.x >= m_width || p.y >= m_height) { VALIDATE_ABORT(); } } #endif T& operator()(int x, int y) { #if VALIDATION CheckOutOfRange(x, y); #endif return m_vec[y][x]; } T const& operator()(int x, int y) const { #if VALIDATION CheckOutOfRange(x, y); #endif return m_vec[y][x]; } T& operator()(pint p) { #if VALIDATION CheckOutOfRange(p); #endif return m_vec[p.y][p.x]; } T const& operator()(pint p) const { #if VALIDATION CheckOutOfRange(p); #endif return m_vec[p.y][p.x]; } T& operator[](pint p) { #if VALIDATION CheckOutOfRange(p); #endif return m_vec[p.y][p.x]; } T const& operator[](pint p) const { #if VALIDATION CheckOutOfRange(p); #endif return m_vec[p.y][p.x]; } vector& operator[](int row) { #if VALIDATION if (row < 0 || row >= m_height) { VALIDATE_ABORT(); } #endif return m_vec[row]; } vector const& operator[](int row) const { #if VALIDATION if (row < 0 || row >= m_height) { VALIDATE_ABORT(); } #endif return m_vec[row]; } bool isIn(int x, int y) const { return x >= 0 && x < m_width&& y >= 0 && y < m_height; } bool isIn(pint p) const { return isIn(p.x, p.y); } bool isOut(int x, int y) const { return x < 0 || x >= m_width || y < 0 || y >= m_height; } bool isOut(pint p) const { return isOut(p.x, p.y); } void disp(ostream& os, int w = 2) { REP(y, m_height) { REP(x, m_width) { os << setw(w) << (*this)(x, y) << " "; } os << endl; } os << endl; } }; template struct dic : public map { bool get(K const& k, V* v) const { auto it = this->find(k); if (it != this->end()) { *v = it->second; return true; } return false; } typename map::const_iterator find_less_than_equal(const K& k) const { auto it = this->lower_bound(k); if (it == this->end()) { if (it == this->begin()) { return this->end(); } return prev(it); } else if (it->first == k) { return it; } else { if (it == this->begin()) { return this->end(); } return prev(it); } } typename map::const_iterator find_greater_than_equal(const K& k) const { return this->lower_bound(k); } }; struct PrintStream { ostream& os_; bool printed_ = false; string space_ = " "; PrintStream(ostream& os, const string& space = " ") : os_(os), space_(space) { } template friend PrintStream& operator<<(PrintStream& ps, T&& v) { if (ps.printed_) { ps.os_ << ps.space_ << v; } else { ps.os_ << v; ps.printed_ = true; } return ps; } PrintStream& operator <<(PrintStream& (*manip)(PrintStream&)) { return (*manip)(*this); } }; PrintStream& endl(PrintStream& ps) { ps.os_ << '\n'; ps.printed_ = false; return ps; } struct OutputStream { ostream& os_; OutputStream(ostream& os) : os_(os) { } template friend OutputStream& operator<<(OutputStream& s, T const& v) { s.os_ << v << '\n'; return s; } }; #include using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using s8 = int8_t; using s16 = int16_t; using s32 = int32_t; using s64 = int64_t; using ints = arr; using pint = pr; using pints = arr; using tint = tr; using tints = arr; using int2 = arr2; const pints around4 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1} }; constexpr int gcd(int a, int b) { if (a < 0) { a = -a; } if (b < 0) { b = -b; } if (a == 0) { return b; } if (b == 0) { return a; } while (int c = a % b) { a = b; b = c; } return b; } constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; } int popcount(int v) { return bitset<64>(v).count(); } int64_t msb(int64_t v) { if (v == 0) return false; v |= (v >> 1); v |= (v >> 2); v |= (v >> 4); v |= (v >> 8); v |= (v >> 16); v |= (v >> 32); return popcount(v) - 1; } #ifdef LOCAL_TEST stringstream inputStream; stringstream outputStream; stringstream errorStream; istream& mis = inputStream; ostream& mos = outputStream; ostream& mes = errorStream; #else istream& mis = cin; ostream& mos = cout; ostream& mes = cerr; #endif template struct TypeInput; template <> struct TypeInput { static void input(int& v, istream& is) { is >> v; } static void input(int& v, istream& is, int add) { is >> v; v += add; } }; template <> struct TypeInput { static void input(int& v, istream& is) { is >> v; } }; template <> struct TypeInput { static void input(char& v, istream& is) { is >> v; } }; template <> struct TypeInput { static void input(string& v, istream& is) { is >> v; } }; template struct TypeInput> { static void input(pr& v, istream& is) { TypeInput::input(v.a, is); TypeInput::input(v.b, is); } static void input(pr& v, istream& is, A&& addA, B&& addB) { TypeInput::input(v.a, is, addA); TypeInput::input(v.b, is, addB); } }; template struct TypeInput> { static void input(tr& v, istream& is) { TypeInput::input(v.a, is); TypeInput::input(v.b, is); TypeInput::input(v.c, is); } static void input(tr& v, istream& is, A&& addA, B&& addB, C&& addC) { TypeInput::input(v.a, is, addA); TypeInput::input(v.b, is, addB); TypeInput::input(v.c, is, addC); } }; template struct TypeInput> { template static void input(arr& v, istream& is, int N, ARGS&&... args) { v.resize(N); REP(i, N) { TypeInput::input(v[i], is, forward(args)...); } } }; template struct TypeInput> { template static void input(arr2& v, istream& is, int H, int W, ARGS&&... args) { v.init(W, H); REP(y, H) { REP(x, W) { TypeInput::input(v(x, y), is, forward(args)...); } } } }; template struct InputParam { tuple args_; InputParam(tuple&& args) : args_(args) {} template ())> operator T() const { T v; apply([&](auto&&... args) { TypeInput::input(v, mis, args...); }, args_); return v; } }; struct inputObject { template ())> operator T() { T v; TypeInput::input(v, mis); return v; } template InputParam operator()(T&&... args) { return InputParam(forward_as_tuple(args...)); } }; struct StdIO { OutputStream out; PrintStream prn; inputObject in; StdIO() : out(mos), prn(mos) { cout << fixed << setprecision(numeric_limits::digits10); cerr << fixed << setprecision(numeric_limits::digits10); } }; struct AlgoMain; #ifdef LOCAL_TEST #include #else struct Main { void Run(int argc, const char* argv[]) { (void)argc; (void)argv; InstanceRun(); } }; #endif constexpr int MOD = 998244353; template struct modint { int raw; modint() { raw = 0; } modint(int v) { if (v < 0) { raw = (v % M) + M; } else if (v >= M) { raw = v % M; } else { raw = v; } } modint operator + (modint v) const { return modint(raw) += v; } modint operator - (modint v) const { return modint(raw) -= v; } modint operator * (modint v) const { return modint(raw) *= v; } modint& operator += (modint v) { raw += v.raw; if (raw >= M) { raw -= M; } return *this; } modint& operator -= (modint v) { raw -= v.raw; if (raw < 0) { raw += M; } return *this; } modint& operator *= (modint v) { raw = (raw * v.raw) % M; return *this; } modint pow(int n) const { return modint::pow(raw, n); } static modint pow(int a, int n) { if (n < 0) { abort(); } int r = 1; while (n) { if (n & 1) { r = (r * a) % M; } a = (a * a) % M; n >>= 1; } return modint(r); } modint inv() const { int a = raw; int b = M; int u = 1; int v = 0; while (b) { int t = a / b; a -= t * b; u -= t * v; swap(a, b); swap(u, v); } u %= M; if (u < 0) { u += M; } return u; } friend istream& operator>>(istream& is, modint& m) { int v; is >> v; m = modint(v); return is; } friend ostream& operator<<(ostream& os, modint const& m) { return os << m.raw; } }; using mint = modint; using mints = arr; using mint2 = arr2; struct AlgoMain : public StdIO { arr arounds; arr> memo; arr center; void Run() { int N = in; pints E = in(N - 1); arounds.init(N); memo.init(N); center.init(N); REP(i, N - 1) { int a = E[i].a - 1; int b = E[i].b - 1; arounds[a].push_back(b); arounds[b].push_back(a); } ints order = ints::Iota(N); order.sort([&](int a, int b) { return arounds[a].size() > arounds[b].size(); }); for (int i : order) { Sum(i); } REP(i, N) { out << center[i]; } } void Sum(int i) { int c = 0; for (int a : arounds[i]) { c += DFS(i, a); } center[i] = c; } int DFS(int from, int to) { if (memo[from].find(to) != memo[from].end()) { return memo[from][to]; } int ans = 0; if (from > to) { ans++; } for (int a : arounds[to]) { if (a == from) { continue; } ans += DFS(to, a); } memo[from][to] = ans; return ans; } };