Quảng trường trung tâm Hàng Châu là nơi có một cây cổ thụ nổi tiếng. Có thể xem cây này là một cây có gốc gồm \(N\) nút, được đánh số từ \(0\) đến \(N-1\), trong đó nút \(0\) là nút gốc.

Một nút không có nút con được gọi là nút lá. Mỗi lần rụng lá, cây chọn một nút đang là nút lá để xóa; trong cùng một ngày, cây có thể rụng lá nhiều lần.

Có \(M\) tình nguyện viên, được đánh số từ \(0\) đến \(M-1\), chịu trách nhiệm bảo vệ cây. Mỗi người độc lập ghi lại tình hình rụng lá trong năm nay như sau:

Mỗi ngày, họ thu thập chỉ số của tất cả những lá vừa rụng trong ngày đó (tức là chỉ số của các nút bị xóa trong ngày), rồi ghi các chỉ số này theo một thứ tự bất kỳ vào sau tất cả các chỉ số đã ghi trong những ngày trước.

Ví dụ, nếu trong ngày đầu tiên các lá \(3\) và \(4\) rụng, tình nguyện viên ghi 3, 4 hoặc 4, 3. Nếu trong ngày thứ hai các lá \(1\) và \(2\) rụng, người đó tiếp tục ghi 1, 2 hoặc 2, 1. Bản ghi cuối cùng có thể là một trong các dãy \((3,4,1,2)\), \((4,3,1,2)\), \((3,4,2,1)\) hoặc \((4,3,2,1)\).

Quá trình kéo dài trong \(K\) ngày, mỗi ngày đều có ít nhất một lá mới rụng, cho đến khi chỉ còn lại nút gốc.

Trong một chuyến du lịch, bạn tình cờ ghé thăm Hàng Châu vào mùa đông lạnh giá. Nhìn những cành cây trơ trụi, bạn hình dung khung cảnh lá rơi tuyệt đẹp và muốn biết trong năm nay mình có thể đã ngắm lá rơi nhiều nhất bao nhiêu ngày. Tuy nhiên, bạn chỉ tìm được bản ghi của \(M\) tình nguyện viên.

Hãy suy ra giá trị lớn nhất có thể của \(K\) phù hợp với tất cả các bản ghi.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int solve(int N, int M, std::vector<int> F,
          std::vector<std::vector<int>> S);

• \(N\): số nút của cây cổ thụ.
• \(M\): số tình nguyện viên.
• \(F\): mảng số nguyên có độ dài \(N\). Với \(1 \le i \le N-1\), \(F[i]\) là chỉ số nút cha của nút \(i\). Luôn có \(F[0]=-1\).
• \(S\): mảng gồm \(M\) mảng số nguyên, mỗi mảng có độ dài \(N-1\). \(S[i][j]\) là chỉ số thứ \(j\) trong bản ghi của tình nguyện viên \(i\); các chỉ số \(i,j\) đều bắt đầu từ \(0\).

Hàm phải trả về một số nguyên biểu diễn giá trị lớn nhất có thể của \(K\), tức số ngày rụng lá lớn nhất có thể theo các quy tắc trên.

Trong mỗi trường hợp kiểm thử, trình chấm có thể gọi hàm này nhiều lần. Mỗi lời gọi phải được xử lý như một kịch bản mới, hoàn toàn độc lập.

Ví dụ

solve(3, 1, {-1, 0, 0}, {{1, 2}})

solve(5, 2, {-1, 0, 0, 1, 1},
      {{1, 2, 3, 4}, {4, 1, 2, 3}})

Ràng buộc

• \(2 \le N \le 10^5\).
• \(1 \le M \le 5\).
• Tổng \(NM\) qua tất cả các lời gọi không vượt quá \(8 \times 10^5\).
• \(F[0]=-1\).
• Với \(1 \le i \le N-1\), \(0 \le F[i] \le i-1\).
• Với \(1 \le i \le M-1\), mảng \(S[i]\) là một hoán vị của \(1,2,\ldots,N-1\).
• Dữ liệu bảo đảm \(F\) mô tả một cây có gốc với nút \(0\) là nút gốc.

Phân nhóm

1. 11 điểm: \(M=1\), \(N \le 10\), tổng \(N \le 30\).
2. 14 điểm: \(N \le 10\), tổng \(N \le 30\).
3. 5 điểm: \(M=1\), \(N \le 1\,000\), tổng \(N \le 2\,000\), \(F[i]=i-1\).
4. 9 điểm: \(M=1\), \(N \le 1\,000\), tổng \(N \le 2\,000\).
5. 5 điểm: \(N \le 1\,000\), tổng \(N \le 2\,000\), \(F[i]=i-1\).
6. 11 điểm: \(N \le 1\,000\), tổng \(N \le 2\,000\).
7. 9 điểm: \(M=1\), \(F[i]=i-1\).
8. 11 điểm: \(M=1\).
9. 9 điểm: \(F[i]=i-1\).
10. 16 điểm: Không có ràng buộc bổ sung.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(T\).
• Với mỗi trường hợp kiểm thử trong \(T\) trường hợp tiếp theo:
  • Dòng \(1\): \(N\ M\).
  • Dòng \(2\): \(F[1]\ F[2]\ \ldots\ F[N-1]\).
  • Dòng \(3+i\) với \(0 \le i \le M-1\): \(S[i][0]\ S[i][1]\ \ldots\ S[i][N-2]\).

Với mỗi trường hợp kiểm thử, trình chấm mẫu in trên một dòng giá trị do hàm solve trả về.

Nguồn

Olympic Tin học Châu Á - Thái Bình Dương 2024 (APIO 2024), bài September. Đề và gói bài chính thức: APIO 2024 Tasks.