Contest Duration: - (local time) (100 minutes) Back to Home

## E - Ranges on Tree Editorial by en_translator

Consider the minimum value of $$\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace$$ in which $$\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)$$ satisfies the conditions in the Problem Statement.

For a given tree, let $$M$$ be the number of leaves (vertices without children), and $$v_1, v_2, \ldots, v_M$$ be the $$M$$ leaves. Then,

for any pair of distinct leaves $$(v_i, v_j)$$, it holds that $$S_{v_i} \cap S_{v_j} = \lbrace v_i \rbrace \cap \lbrace v_j \rbrace = \emptyset$$,

so, by the condition in the Problem Statement, it should be that

for any pair of distinct leaves $$(v_i, v_j)$$, it holds that $$[L_{v_i}, R_{v_i}] \cap [L_{v_j}, R_{v_j}] = \emptyset$$.

Thus, $$\lbrace L_{v_1}, L_{v_2}, \ldots, L_{v_M} \rbrace$$ should contain at least $$M$$ distinct positive integers (same holds for $$\lbrace R_{v_1}, R_{v_2}, \ldots, R_{v_M} \rbrace$$). Therefore, the minimum value of $$\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace$$ that can be achieved is at least $$M$$.

Conversely, $$\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M$$ can be achieved. Indeed, we can construct $$\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)$$ achieving $$\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M$$ as follows.

1. First, perform Depth-First Search (DFS) from the root, Vertex $$1$$. For each of $$M$$ leaves, give it a nickname of Leaf $$1$$, Leaf $$2$$, $$\ldots$$, Leaf $$M$$, in the order of visiting during the DFS.

2. For each $$i =1, 2, \ldots, N$$, let $$L_i$$ and $$R_i$$ be the minimum and maximum value of the nicknames of the leaves included in the subtree rooted at Vertex $$i$$.

Finding the minimum and maximum value of the nicknames of the leaves included in the subtree rooted at Vertex $$i$$ in Step 2. can be achieved in a total of $$O(N)$$ time with DFS.

Since the nicknames of the leaves was given in the DFS, for each $$i = 1, 2, \ldots, N$$, the set of nicknames of leaves in the subtree rooted at Vertex $$i$$ is a set of consecutive integers. Therefore, the set of nicknames of leaves in the subtree rooted at Vertex $$i$$ is $$[L_i, R_i]$$. Moreover, the nicknames of leaves are pairwise distinct, so $$\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)$$ constructed by the procedure above indeed satisfies the condition in the Problem Statement.

Hence, the problem can be solved in a total of $$\mathrm{O}(N)$$ time.

The following is a sample code in 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;
}


posted:
last update: