1. Phân tích bài toán

• Giới hạn: ~n \le k \le 10~. Với giới hạn rất nhỏ này, ta hoàn toàn có thể duyệt vét cạn toàn bộ các cách gán điểm.

2. Thuật toán

• Bước 1: Chọn ~n~ điểm số phân biệt trong tập ~\{1, 2, \dots, k\}~. Số cách chọn là ~\binom{k}{n} \le \binom{10}{5} = 252~ cách. Ta dùng quay lui để sinh ra tất cả các tập con ~n~ phần tử tăng dần.
• Bước 2: Với mỗi tập gồm ~n~ điểm được chọn, ta thử tất cả ~n!~ hoán vị gán cho ~n~ học sinh bằng hàm next_permutation (~n! \le 10! = 3.628.800~ trong trường hợp tệ nhất, nhưng ở đây ~n~ điểm đã chọn nên với mỗi tập chỉ cần gán và kiểm tra).
• Bước 3: Kiểm tra điều kiện:
  • Duyệt qua ~n - 1~ cạnh ~(u, v)~ của cây bạn bè.
  • Nếu ~a_u > a_v~ thì phải có ~b_u > b_v~.
  • Nếu thỏa mãn tất cả ~n - 1~ cạnh thì tăng biến đếm kết quả.

3. Độ phức tạp

• Số trạng thái duyệt tối đa: ~\binom{k}{n} \times n! = A_k^n \le A_{10}^{10} = 3.628.800~.
• Thời gian chạy dưới 0.2s, hoàn toàn đạt điểm tối đa cho giới hạn ~k \le 10~.