E - Ranges on Tree 解説 by leaf1415
問題文中の条件を満たす \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) が達成できる \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace\) の最小値を考えます。
与えられた木の、葉(すなわち、子を持たない頂点)の個数を \(M\) とし、 \(M\) 個の葉を \(v_1, v_2, \ldots, v_M\) とします。 このとき、
任意の異なる \(2\) つの葉 \(v_i, v_j\) について、 \(S_{v_i} \cap S_{v_j} = \lbrace v_i \rbrace \cap \lbrace v_j \rbrace = \emptyset\)
であるので、問題文中の条件より
任意の異なる \(2\) つの葉 \(v_i, v_j\) について \([L_{v_i}, R_{v_i}] \cap [L_{v_j}, R_{v_j}] = \emptyset\)
でなければなりません。 よって、\(\lbrace L_{v_1}, L_{v_2}, \ldots, L_{v_M} \rbrace\) には少なくとも異なる \(M\) 個の正の整数が含まれなければなりません( \(\lbrace R_{v_1}, R_{v_2}, \ldots, R_{v_M} \rbrace\) で考えても同様)。 したがって、達成できる \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace\) の最小値は \(M\) 以上です。
反対に、\(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M\) は達成できます。 実際、\(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M\) を達成する \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) を以下のようにして構成することができます。
まず、根である頂点 \(1\) から深さ優先探索を行います。 \(M\) 個の葉について、深さ優先探索で訪れたのが早い順に、 葉 \(1\) 、葉 \(2\) 、\(\ldots\) 、葉 \(M\) とあだ名をつけます。
\(i =1, 2, \ldots, N\) について、\(L_i\) と \(R_i\) をそれぞれ頂点 \(i\) の部分木に含まれる葉のあだ名の最小値と最大値とします。
手順 2. で各頂点の部分木に含まれる葉のあだ名の最小値・最大値を求めるのは、深さ優先探索によってまとめて \(\mathrm{O}(N)\) 時間で行えます。
葉のあだ名は深さ優先探索によって与えたので、\(i = 1, 2, \ldots, N\) について、頂点 \(i\) の部分木に含まれる葉のあだ名の集合は、連続するいくつかの整数からなる集合となります。 よって、 頂点 \(i\) の部分木に含まれる葉のあだ名の集合は \([L_i, R_i]\) です。 このことと、葉のあだ名は葉ごとに異なることから、上記の手順で構成した \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) がたしかに問題文中の条件を満たすことが確かめられます。
以上より、本問題を \(\mathrm{O}(N)\) 時間で解くことができます。
以下にC++言語による正解例を記載します。
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> G[200005];
int L[200005], R[200005];
int leaf[200005];
int id = 0;
void dfs(int v, int p)
{
if(v != 1 && G[v].size() == 1){
leaf[v] = ++id;
return;
}
for(auto u : G[v]) if(u != p) dfs(u, v);
}
void dfs2(int v, int p)
{
if(leaf[v]){
L[v] = R[v] = leaf[v];
return;
}
L[v] = 1e9, R[v] = -1e9;
for(auto u : G[v]){
if(u == p) continue;
dfs2(u, v);
L[v] = min(L[v], L[u]);
R[v] = max(R[v], R[u]);
}
}
int main(void)
{
cin >> n;
int u, v;
for(int i = 1; i <= n-1; i++){
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1);
dfs2(1, -1);
for(int i = 1; i <= n; i++) cout << L[i] << " " << R[i] << "\n";
return 0;
}
投稿日時:
最終更新: