Editorial for Xây dựng cây

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Subtask 1: Ta liệt kê các đồ thị dạng cây có thể với $N \le 5$ ~N \le 5~ đỉnh và kiểm tra với từng test case.

Độ phức tạp: $O(T.N)$ ~O(T.N)~

Subtask 2: Gọi $\mathrm{max_A}$ ~\mathrm{max_A}~ là giá trị $A_i$ ~A_i~ lớn nhất và $count_j$ ~count_j~ là số lượng chỉ số $i$ ~i~ thỏa mãn $A_i=j$ ~A_i=j~. Khi đó, điều kiện cần và đủ của mảng $A$ ~A~ để có thể xây dựng cây là:

$\lceil \frac{\mathrm{max_A}}{2} \rceil \le A_i < N$ với mọi $1 \le i \le N$ ~1 \le i \le N~.
$count_j \ge 2$ ~count_j \ge 2~ với mọi $j > \lceil \frac{\mathrm{max_A}}{2} \rceil$ .
$count_{\lceil \frac{max_A}{2} \rceil} = 1$ nếu $\mathrm{max_A}$ ~\mathrm{max_A}~ chẵn và $count_{\lceil \frac{max_A}{2} \rceil} = 2$ nếu $\mathrm{max_A}$ ~\mathrm{max_A}~ lẻ.

Độ phức tạp: $O(T.N)$ ~O(T.N)~

Editorial for Xây dựng cây

Comments