問題

E – Ranges on Tree

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

atcoder.jp

記録

• 2022/3/7　バーチャル参加。解法わからず。

解法

• あとで書く

コード例

#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;
}