TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Ranges on Tree

問題

E – Ranges on Tree
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
const int INF = 1001001001;

int N;
vector<vector<int>> edges;
vector<int> leafs;
vector<P> ans;
int id = 0;

void dfs(int c, int p) {
  if(c != 0 && edges[c].size() == 1) {
    id++;
    ans[c] = make_pair(id, id);
    return;
  }
  int n = edges[c].size();
  rep(i, n) {
    int nxt = edges[c][i];
    if(nxt != p) {
      dfs(nxt, c);
    }
  }
  return;
}

void dfs2(int c, int p) {
  if(leafs[c] != 0) {
    ans[c] = make_pair(leafs[c], leafs[c]);
    return;
  }
  int n = edges[c].size();
  rep(i, n) {
    int nxt = edges[c][i];
    if(nxt == p) {
      continue;
    }
    dfs2(nxt, c);
    int f = min(ans[c].first, ans[nxt].first);
    int s = max(ans[c].second, ans[nxt].second);
    ans[c] = make_pair(f, s);
  }
  return;
}

int main() {
  cin >> N;
  edges.resize(N);
  leafs.resize(N);
  ans.resize(N);

  rep(i, N) { ans[i] = make_pair(INF, -1); }

  for(int i = 0; i < N - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }

  dfs(0, -1);

  dfs2(0, -1);
  rep(i, N) { cout << ans[i].first << " " << ans[i].second << endl; }

  return 0;
}