結果
問題 | No.2427 Tree Distance Two |
ユーザー |
![]() |
提出日時 | 2023-08-18 22:07:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 914 ms / 2,000 ms |
コード長 | 30,892 bytes |
コンパイル時間 | 2,299 ms |
コンパイル使用メモリ | 211,240 KB |
最終ジャッジ日時 | 2025-02-16 10:05:27 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#line 1 "playspace/main.cpp"#include <bits/stdc++.h>#line 8 "library/gandalfr/other/io_supporter.hpp"template <typename T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {for (int i = 0; i < (int)v.size(); i++)os << v[i] << (i + 1 != (int)v.size() ? " " : "");return os;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {for (const T &x : st) {std::cout << x << " ";}return os;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {for (const T &x : st) {std::cout << x << " ";}return os;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::deque<T> &dq) {for (const T &x : dq) {std::cout << x << " ";}return os;}template <typename T1, typename T2>std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {os << p.first << ' ' << p.second;return os;}template <typename T>std::ostream &operator<<(std::ostream &os, std::queue<T> &q) {int sz = q.size();while (--sz) {os << q.front() << ' ';q.push(q.front());q.pop();}os << q.front();q.push(q.front());q.pop();return os;}template <typename T>std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (T &in : v)is >> in;return is;}template <typename T1, typename T2>std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {is >> p.first >> p.second;return is;}#line 8 "library/gandalfr/graph/graph.hpp"#line 3 "library/gandalfr/data_structure/union_find.hpp"#line 6 "library/gandalfr/data_structure/union_find.hpp"class union_find {private:int N;mutable std::vector<int> par;std::vector<int> nxt;int group_num; // 集合の数public:union_find() : N(0), group_num(0) {}union_find(int n) : N(n), par(n, -1), nxt(n), group_num(n) {std::iota(nxt.begin(), nxt.end(), 0);}/*** @brief 頂点を n 個に増やす* @attention 小さくはできない*/void expand(int n) {if (n <= N)return;par.resize(n, -1);nxt.resize(n);for (int i = N; i < n; ++i)nxt[i] = i;group_num += n - N;N = n;}int leader(int x) const {return (par[x] < 0 ? x : par[x] = leader(par[x]));}bool same(int x, int y) const { return leader(x) == leader(y); }bool merge(int x, int y) {if ((x = leader(x)) == (y = leader(y)))return false;if (-par[x] > -par[y])std::swap(x, y);par[x] += par[y];par[y] = x;std::swap(nxt[x], nxt[y]);group_num--;return true;}/*** @brief x の属するグループのサイズを返す*/int size(int x) const { return -par[leader(x)]; }/*** @brief すべてのノードの数*/int size() const { return N; }std::vector<int> contained_group(int x) const {std::vector<int> ret{x};for (int cu = nxt[x]; cu != ret[0]; cu = nxt[cu])ret.push_back(cu);return ret;}int count_groups() const { return group_num; }std::vector<std::vector<int>> all_groups() const {std::vector<std::vector<int>> result;result.reserve(group_num);std::vector<bool> used(N, false);for (int i = 0; i < N; ++i) {if (!used[i]) {result.emplace_back(contained_group(i));for (int x : result.back()) {used[x] = true;}}}return result;}};#line 3 "library/gandalfr/math/matrix.hpp"#line 8 "library/gandalfr/math/matrix.hpp"template <class T> class matrix {private:int H, W;std::valarray<std::valarray<T>> table;enum rowtrans_operation_name { SCALE, SWAP, ADD };struct rowtrans_operation {int op, tar, res;T scl;};using operations_history = std::vector<rowtrans_operation>;public:matrix() = default;matrix(int _H, int _W, T val = 0): H(_H), W(_W), table(std::valarray<T>(val, _W), _H) {}matrix(const std::vector<std::vector<T>> &vv): H(vv.size()), W(vv[0].size()), table(std::valarray<T>(W), H) {for (int i = 0; i < H; i++)for (int j = 0; j < W; j++)table[i][j] = vv[i][j];}matrix(const std::valarray<std::valarray<T>> &vv): H(vv.size()), W(vv[0].size()), table(vv) {}/*** @brief 行列をリサイズする。* @param val 拡張部分の値*/void resize(int _H, int _W, T val = 0) {H = _H, W = _W;table.resize(_H, std::valarray<T>(val, _H));}int size_H() const { return H; }int size_W() const { return W; }void transpose() {matrix<T> ret(W, H);for (int i = 0; i < H; i++)for (int j = 0; j < W; j++)ret.table[j][i] = table[i][j];*this = std::move(ret);}void row_assign(int i, const std::valarray<T> &row) {assert(W == (int)row.size());table[i] = std::move(row);}void row_swap(int i, int j) {assert(0 <= i && i < H);assert(0 <= j && j < H);table[i].swap(table[j]);}/*** @attention O(n^3)* @attention 整数型では正しく計算できない。double や fraction を使うこと。* @attention 枢軸選びをしていないので double では誤差が出るかも。*/operations_history sweep_method() {operations_history hist;T ret = 1;for (int h = 0, w = 0; h < H && w < W; w++) {if (table[h][w] == 0) {for (int piv = h + 1; piv < H; piv++) {if (table[piv][w] != 0) {hist.push_back({SWAP, h, piv, 0});row_swap(h, piv);break;}}if (table[h][w] == 0) {continue;}}T inv = 1 / table[h][w];hist.push_back({SCALE, -1, w, inv});table[h] *= inv;for (int j = h + 1; j < H; j++) {hist.push_back({ADD, h, j, -table[j][w]});table[j] -= table[h] * table[j][w];}h++;}return hist;}int rank() {auto U(*this);U.sweep_method();int r = 0;for (int i = 0; i < H; ++i) {for (int j = i; j < W; ++j) {if (U.table[i][j] != 0) {r++;break;}}}return r;}T determinant() const {assert(H == W);matrix<T> U(*this);T det = 1;auto hist = U.sweep_method();if (U.table[H - 1][H - 1] == 0)return 0;for (auto &[op, tar, res, scl] : hist) {switch (op) {case SCALE:det /= scl;break;case SWAP:det *= -1;break;}}return det;}std::vector<T> solve_system_of_equations(const std::vector<T> &y) {assert(H == W);std::vector<T> x(y);matrix<T> U(*this);auto hist = U.sweep_method();if (U.table[H - 1][H - 1] == 0)return {};for (auto &[op, tar, res, scl] : hist) {switch (op) {case SCALE:x[res] *= scl;break;case SWAP:std::swap(x[tar], x[res]);break;case ADD:x[res] += x[tar] * scl;break;}}for (int i = H - 1; i >= 0; --i) {for (int j = 0; j < i; ++j) {x[j] -= U.table[j][i] * x[i];}}return x;}matrix<T> inverse() {assert(H == W);matrix<T> INV(matrix<T>::E(H)), U(*this);auto hist = U.sweep_method();if (U.table[H - 1][H - 1] == 0)return matrix<T>(0, 0);for (auto &[op, tar, res, scl] : hist) {switch (op) {case SCALE:INV.table[res] *= scl;break;case SWAP:std::swap(INV.table[tar], INV.table[res]);break;case ADD:INV.table[res] += INV.table[tar] * scl;break;}}for (int i = H - 1; i >= 0; --i) {for (int j = 0; j < i; ++j) {INV.table[j] -= INV.table[i] * U.table[j][i];}}return INV;}void print() const {for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) {std::cout << table[i][j] << (j == W - 1 ? "" : " ");}std::cout << std::endl;}}matrix<T> &operator+=(const matrix<T> &a) {this->table += a.table;return *this;}matrix<T> &operator-=(const matrix<T> &a) {this->table -= a.table;return *this;}matrix<T> &operator*=(const T &a) {this->table *= a;return *this;}matrix<T> &operator*=(const matrix<T> &a) {assert(W == a.H);matrix<T> a_t(a), ret(H, a.W);a_t.transpose();for (int i = 0; i < H; i++) {for (int j = 0; j < a_t.H; j++) {ret.table[i][j] = (table[i] * a_t.table[j]).sum();}}*this = std::move(ret);return *this;}matrix<T> &operator/=(const T &a) {this->table /= a;return *this;}/*** @brief 行列の冪乗。* @param n 指数* @attention n が 0 なら単位行列。* @attention 演算子の優先度に注意。*/matrix<T> operator^=(long long n) {assert(H == W);if (n == 0)return *this = E(H);n--;matrix<T> x(*this);while (n) {if (n & 1)*this *= x;x *= x;n >>= 1;}return *this;}matrix<T> operator+() { return *this; }matrix<T> operator-() { return matrix<T>(*this) *= -1; }matrix<T> operator+(const matrix<T> &a) { return matrix<T>(*this) += a; }matrix<T> operator-(const matrix<T> &a) { return matrix<T>(*this) -= a; }template <typename S> matrix<T> operator*(const S &a) {return matrix<T>(*this) *= a;}matrix<T> operator/(const T &a) { return matrix<T>(*this) /= a; }matrix<T> operator^(long long n) { return matrix<T>(*this) ^= n; }friend std::istream &operator>>(std::istream &is, matrix<T> &mt) {for (auto &arr : mt.table)for (auto &x : arr)is >> x;return is;}T &operator()(int h, int w) {assert(0 <= h && h < H && 0 <= w && w <= W);return table[h][w];}/*** @brief サイズ n の単位行列。*/static matrix<T> E(int N) {matrix<T> ret(N, N);for (int i = 0; i < N; i++)ret.table[i][i] = 1;return ret;}};#line 3 "library/gandalfr/graph/edge.hpp"namespace internal {template <class DERIVED, class WEIGHT> struct _base_edge {int from;int to;WEIGHT cost;int id;_base_edge() {}_base_edge(int _from, int _to, WEIGHT _cost, int _id): from(_from), to(_to), cost(_cost), id(_id) {}friend bool operator>(const _base_edge &e1, const _base_edge &e) {return e1.compare(e) > 0;}friend bool operator>=(const _base_edge &e1, const _base_edge &e) {return e1.compare(e) >= 0;}friend bool operator<(const _base_edge &e1, const _base_edge &e) {return e1.compare(e) < 0;}friend bool operator<=(const _base_edge &e1, const _base_edge &e) {return e1.compare(e) <= 0;}friend std::ostream &operator<<(std::ostream &os,const _base_edge<DERIVED, WEIGHT> &e) {e.print(os);return os;}_base_edge &operator=(const _base_edge &e) = default;virtual ~_base_edge() = default;DERIVED minmax() const {auto [f, t] = std::minmax(from, to);return {f, t, cost, id};}DERIVED reverse() const { return {to, from, cost, id}; }operator int() const { return to; }protected:virtual void print(std::ostream &os) const = 0;virtual int compare(const _base_edge &e) const = 0;};} // namespace internaltemplate <class WEIGHT>struct edge : public internal::_base_edge<edge<WEIGHT>, WEIGHT> {using internal::_base_edge<edge<WEIGHT>, WEIGHT>::_base_edge;protected:void print(std::ostream &os) const override {os << this->from << " " << this->to << " " << this->cost;}int compare(const internal::_base_edge<edge<WEIGHT>, WEIGHT> &e) const override {if (this->cost == e.cost) {if (this->from == e.from)return this->to - e.to;return this->from - e.from;}return this->cost - e.cost;}};template <> struct edge<int> : public internal::_base_edge<edge<int>, int> {static inline const int cost = 1;using internal::_base_edge<edge<int>, int>::_base_edge;edge(int _from, int _to, int _id): _base_edge<edge<int>, int>(_from, _to, 0, _id) {}protected:void print(std::ostream &os) const override {os << this->from << " " << this->to;}int compare(const internal::_base_edge<edge<int>, int> &e) const override {if (this->from == e.from)return this->to - e.to;return this->from - e.from;}};#line 12 "library/gandalfr/graph/graph.hpp"/*** @brief グラフを管理するクラス。* @tparam WEIGHT int なら重みなし、そうでないなら重みつきグラフ* @tparam is_directed 有向グラフかとうか*/template <typename WEIGHT, bool is_directed> class graph {private:int N;std::vector<std::vector<edge<WEIGHT>>> G;std::vector<edge<WEIGHT>> E;union_find uf;WEIGHT W = 0;mutable std::vector<bool> visited; // dfs / bfs のための領域bool forest_flag = true;const WEIGHT WEIGHT_MAX = std::numeric_limits<WEIGHT>::max();void reset_visited_flag(int node) const {for (int x : uf.contained_group(node))visited[x] = false;}void reset_visited_flag() const { visited.assign(N, false); }public:graph() : N(0){};graph(int n) : N(n), G(n), uf(n), visited(n){};/*** @brief ノードの数をn個まで増やす* @param n サイズ* @attention 今のノード数より小さい数を渡したとき、変化なし*/void expand(int n) {if (n <= N)return;N = n;G.resize(n);visited.resize(n);uf.expand(n);}/*** @return ノードの数*/int count_nodes() const { return N; }/*** @return 辺の数*/int count_edges() const { return E.size(); }/*** @param n ノード番号* @return ノード n からの隣接頂点のリストの const 参照*/const std::vector<edge<WEIGHT>> &operator[](int n) const { return G[n]; }/*** @return グラフ全体の辺のリストの const 参照*/const std::vector<edge<WEIGHT>> &edges() const { return E; }/*** @param x ノード番号* @param y ノード番号* @return x, y が連結かどうか*/bool are_connected(int x, int y) const { return uf.same(x, y); }/*** @return 連結成分の数*/int count_connected_components() const { return uf.count_groups(); }/*** @return 連結成分のリストのリスト*/std::vector<std::vector<int>> weakly_connected_components() const {return uf.all_groups();}/*** @return 木か*/bool is_tree() const { return forest_flag && uf.count_groups() == 1; }/*** @return 森か*/bool is_forest() const { return forest_flag; }/*** @return グラフの重み*/WEIGHT weight() const { return W; }/*** @param e 辺* @attention 渡した辺の id は保持される*/void add_edge(const edge<WEIGHT> &e) {forest_flag &= uf.merge(e.from, e.to);G[e.from].emplace_back(e);if (!is_directed && e.from != e.to)G[e.to].emplace_back(e.reverse());if constexpr (is_directed) {E.emplace_back(e);} else {E.emplace_back(e.minmax());}W += e.cost;}/*** @attention 辺の id は、(現在の辺の本数)番目 が振られる* @attention WEIGHT が int だとエラー*/void add_edge(int from, int to, WEIGHT cost) {static_assert(!std::is_same<WEIGHT, int>::value);add_edge({from, to, cost, (int)E.size()});}/*** @attention 辺の id は、(現在の辺の本数)番目 が振られる* @attention WEIGHT が int 以外だとエラー*/void add_edge(int from, int to) {static_assert(std::is_same<WEIGHT, int>::value);add_edge({from, to, (int)E.size()});}/*** @brief グラフを連結なグラフに分けてリストにして返す* @example auto[Gs, gr, nd] = G.decompose();* @returns* 1.グラフのリスト* 2.各ノードがグラフのリストの何番目に属するか* 3.各ノードがグラフのどのノードになっているか*/std::tuple<std::vector<graph>, std::vector<int>, std::vector<int>>decompose() const {std::vector<graph> Gs(uf.count_groups());std::vector<std::vector<int>> groups(uf.all_groups());std::vector<int> group_id(N), node_id(N);for (int i = 0; i < (int)groups.size(); i++) {Gs[i].expand(groups[i].size());for (int j = 0; j < (int)groups[i].size(); j++) {group_id[groups[i][j]] = i;node_id[groups[i][j]] = j;}}for (auto e : E) {int id = group_id[e.from];e.from = node_id[e.from];e.to = node_id[e.to];Gs[id].add_edge(e);}return std::make_tuple(std::move(Gs), std::move(group_id),std::move(node_id));}/*** @brief グラフを隣接行列に変換* @param invalid 辺のないときの値* @attention 自己ループが含まれていない限り、対角成分は 0* @attention 多重辺を持たないと仮定*/matrix<WEIGHT> to_adjajency(WEIGHT invalid = 0) const {matrix<WEIGHT> ret(N, N, invalid);for (int i = 0; i < N; i++)ret(i, i) = 0;for (int i = 0; i < N; i++)for (auto &e : G[i])ret(i, e.to) = e.cost;return ret;}/*** @brief 行きがけ順に bfs*/std::vector<int> preorder(int start) const {std::vector<int> result;std::stack<std::pair<int, int>> stk;reset_visited_flag(start);visited[start] = true;stk.push({start, 0});while (!stk.empty()) {auto &[cu, idx] = stk.top();if (idx == 0)result.push_back(cu);if (idx == G[cu].size()) {stk.pop();} else {int to = G[cu][idx++];if (!visited[to]) {visited[to] = true;stk.push({to, 0});}}}return result;}/*** @brief 通りがけ順に bfs*/std::vector<int> inorder(int start) const {std::vector<int> result;std::stack<std::pair<int, int>> stk;reset_visited_flag(start);visited[start] = true;stk.push({start, 0});while (!stk.empty()) {auto &[cu, idx] = stk.top();if (idx == G[cu].size()) {stk.pop();result.push_back(cu);} else {int to = G[cu][idx++];if (!visited[to]) {visited[to] = true;stk.push({to, 0});result.push_back(cu);}}}return result;}/*** @brief 帰りがけ順に bfs*/std::vector<int> postorder(int start) const {std::vector<int> result;std::stack<std::pair<int, int>> stk;reset_visited_flag(start);visited[start] = true;stk.push({start, 0});while (!stk.empty()) {auto &[cu, idx] = stk.top();if (idx == G[cu].size()) {stk.pop();result.push_back(cu);} else {int to = G[cu][idx++];if (!visited[to]) {visited[to] = true;stk.push({to, 0});}}}return result;}private:using PAIR = std::pair<WEIGHT, int>;using Dijkstra_queue =std::priority_queue<PAIR, std::vector<PAIR>, std::greater<PAIR>>;void run_bfs(std::vector<int> &dist, std::queue<int> &q) const {while (!q.empty()) {int cu = q.front();q.pop();for (auto &e : G[cu]) {if (dist[e.to] != WEIGHT_MAX)continue;dist[e.to] = dist[cu] + 1;q.push(e.to);}}}void run_Dijkstra(std::vector<WEIGHT> &dist, Dijkstra_queue &q) const {while (!q.empty()) {WEIGHT cur_dist = q.top().first;int cu = q.top().second;q.pop();if (visited[cu])continue;visited[cu] = true;for (auto &e : G[cu]) {WEIGHT alt = cur_dist + e.cost;if (dist[e.to] <= alt)continue;dist[e.to] = alt;q.push({alt, e.to});}}}public:/*** @brief 最短距離を計算する* @param start_node 始点* @param invalid 到達不能な頂点に格納される値* @return 各ノードまでの最短距離のリスト*/std::vector<WEIGHT> distances(int start_node, WEIGHT invalid) const {std::vector<WEIGHT> dist(N, WEIGHT_MAX);dist[start_node] = 0;if constexpr (std::is_same<WEIGHT, int>::value) {// BFS algorithmstd::queue<int> q;q.push(start_node);run_bfs(dist, q);} else {// Dijkstra's algorithmDijkstra_queue q;q.push({0, start_node});reset_visited_flag(start_node);run_Dijkstra(dist, q);}for (auto &x : dist)if (x == WEIGHT_MAX)x = invalid;return dist;}public:/*** @brief 最短距離を計算する* @param start_nodes 始点のリスト* @param invalid 到達不能な頂点に格納される値* @return 各ノードまでの最短距離のリスト*/std::vector<WEIGHT> distances(const std::vector<int> &start_nodes,WEIGHT invalid) const {std::vector<WEIGHT> dist(N, WEIGHT_MAX);for (auto &x : start_nodes)dist[x] = 0;if constexpr (std::is_same<WEIGHT, int>::value) {// BFS algorithmstd::queue<int> q;for (auto &x : start_nodes)q.push(x);run_bfs(dist, q);} else {// Dijkstra's algorithmDijkstra_queue q;std::set<int> st;for (auto &x : start_nodes) {q.push({0, x});st.insert(uf.leader(x));}for (auto &x : st) {reset_visited_flag(x);}run_Dijkstra(dist, q);}for (auto &x : dist)if (x == WEIGHT_MAX)x = invalid;return dist;}matrix<WEIGHT> distances_from_all_nodes(WEIGHT invalid = -1) {auto mt(to_adjajency(WEIGHT_MAX));int N = mt.size_H();for (int k = 0; k < N; k++) // 経由する頂点for (int i = 0; i < N; i++) // 始点for (int j = 0; j < N; j++) // 終点if (mt(i, k) != WEIGHT_MAX && mt(k, j) != WEIGHT_MAX)mt(i, j) = std::min(mt(i, j), mt(i, k) + mt(k, j));for (int i = 0; i < N; ++i)for (int j = 0; j < N; ++j)if (mt(i, j) == WEIGHT_MAX)mt(i, j) = invalid;return mt;}/*** @brief 復元付き最短経路* @attention 到達可能でないとき、空の配列で返る*/std::vector<edge<WEIGHT>> shortest_path(int start_node, int end_node) {if (start_node == end_node)return {};auto dist = distances(start_node, WEIGHT_MAX);if (dist[end_node] == WEIGHT_MAX)return {};auto R(this->reverse());reset_visited_flag(end_node);visited[end_node] = true;int cu = end_node;std::vector<edge<WEIGHT>> route;while (cu != start_node) {for (auto e : R[cu]) {if (visited[e.to])continue;if (dist[cu] - e.cost == dist[e.to]) {visited[cu = e.to] = true;route.push_back(e.reverse());break;}}}std::reverse(route.begin(), route.end());return route;}WEIGHT diameter() const {static_assert(!is_directed);assert(is_tree());std::vector<WEIGHT> dist(distances(0, -1));dist = distances(std::max_element(dist.begin(), dist.end()) - dist.begin(), -1);return *std::max_element(dist.begin(), dist.end());}graph reverse() const {if constexpr (!is_directed) {return *this;} else {graph ret(N);for (auto &e : E) {ret.add_edge(e.reverse());}return ret;}}std::vector<int> topological_sort() {static_assert(is_directed);std::vector<int> indeg(N, 0), sorted;for (int to : E)indeg[to]++;std::queue<int> q;for (int i = 0; i < N; i++)if (!indeg[i])q.push(i);while (!q.empty()) {int cu = q.front();q.pop();for (int to : G[cu]) {if (!--indeg[to])q.push(to);}sorted.push_back(cu);}return sorted;}/*** @return 最小全域森*/graph minimum_spanning_forest() const {static_assert(!is_directed);graph ret(N);std::vector<edge<WEIGHT>> tmp(edges());std::sort(tmp.begin(), tmp.end());for (auto &e : tmp)if (!ret.are_connected(e.from, e.to))ret.add_edge(e);return ret;}private:/*** @see https://ei1333.github.io/luzhiled/snippets/graph/lowlink.html* @attention 非連結でも動作*/int run_lowlink(int idx, int k, int par, std::vector<int> &ord,std::vector<int> &low, std::vector<edge<WEIGHT>> &brds,std::vector<int> &apts) {visited[idx] = true;ord[idx] = k++;low[idx] = ord[idx];bool is_apt = false;int cnt = 0;for (auto &e : G[idx]) {if (!visited[e.to]) {++cnt;k = run_lowlink(e.to, k, idx, ord, low, brds, apts);low[idx] = std::min(low[idx], low[e.to]);is_apt |= ~par && low[e.to] >= ord[idx];if (ord[idx] < low[e.to]) {brds.emplace_back(e.minmax());}} else if (e.to != par) {low[idx] = std::min(low[idx], ord[e.to]);}}is_apt |= par == -1 && cnt > 1;if (is_apt)apts.push_back(idx);return k;}public:std::pair<std::vector<edge<WEIGHT>>, std::vector<int>> lowlink() {static_assert(!is_directed);std::vector<edge<WEIGHT>> brds;std::vector<int> apts, ord(N, 0), low(N, 0);reset_visited_flag();int k = 0;for (int i = 0; i < N; i++) {if (!visited[i])k = run_lowlink(i, k, -1, ord, low, brds, apts);}return {brds, apts};}void print() const {std::cout << this->N << " " << this->E.size() << std::endl;for (const edge<WEIGHT> &e : this->E)std::cout << e << std::endl;}};#line 4 "playspace/main.cpp"using namespace std;using ll = long long;const int INF = 1001001001;const int MAXINT = std::numeric_limits<int>::max();const int MININT = std::numeric_limits<int>::min();const ll INFLL = 1001001001001001001;const ll MAXLL = std::numeric_limits<ll>::max();const ll MINLL = std::numeric_limits<ll>::min();const ll MOD = 1000000007;const ll _MOD = 998244353;#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)#define all(a) (a).begin(),(a).end()#define LF cout << endl#ifdef ENABLE_MULTI_FOR#define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it)#endiftemplate<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; }int main(void){int N;cin >> N;graph<int, false> G(N);rep(i,0,N-1) {int a, b;cin >> a >> b;G.add_edge(a-1, b-1);}rep(i,0,N) {int sum = 0;rep(j,0,G[i].size()) sum += G[G[i][j].to].size();cout << sum - G[i].size() << endl;}}