Vétyem Woods là một khu rừng nổi tiếng với nhiều cây cối đủ sắc màu. Một trong những cây dẻ gai cổ nhất và cao nhất có tên là Ős Vezér.

Cây Ős Vezér được mô hình hóa bằng \(N\) đỉnh và \(N-1\) cạnh. Các đỉnh được đánh số từ \(0\) đến \(N-1\), các cạnh từ \(1\) đến \(N-1\). Mỗi cạnh nối hai đỉnh khác nhau. Cụ thể, cạnh \(i\) (\(1\le i<N\)) nối đỉnh \(i\) với đỉnh \(P[i]\), trong đó \(0\le P[i]<i\). Đỉnh \(P[i]\) được gọi là cha của đỉnh \(i\), và đỉnh \(i\) là con của đỉnh \(P[i]\).

Mỗi cạnh có một màu. Có \(M\) màu có thể có, đánh số từ \(1\) đến \(M\). Màu của cạnh \(i\) là \(C[i]\). Các cạnh khác nhau có thể cùng màu.

Trong định nghĩa trên, \(i=0\) không tương ứng với cạnh nào. Để thuận tiện, đặt \(P[0]=-1\) và \(C[0]=0\).

Ví dụ, giả sử cây có \(N=18\) đỉnh và \(M=3\) màu, với \(17\) cạnh được mô tả bởi:

Cây được mô tả trong hình sau:

Árpád là một người kiểm lâm tài năng, thích nghiên cứu những phần của cây gọi là cây con. Với mỗi \(r\) thỏa mãn \(0\le r<N\), cây con của đỉnh \(r\) là tập \(T(r)\) các đỉnh có những tính chất sau:

• Đỉnh \(r\) thuộc \(T(r)\).
• Khi một đỉnh \(x\) thuộc \(T(r)\) thì mọi đỉnh con của \(x\) cũng thuộc \(T(r)\).
• Không có đỉnh nào khác thuộc \(T(r)\).

Kích thước của tập \(T(r)\) được ký hiệu là \(|T(r)|\).

Gần đây, Árpád phát hiện một tính chất phức tạp nhưng thú vị của cây con. Phát hiện này cần rất nhiều thử nghiệm bằng giấy bút, và anh ấy nghĩ bạn cũng có thể cần làm như vậy để hiểu tính chất đó. Anh ấy sẽ đưa ra nhiều ví dụ để bạn phân tích chi tiết.

Giả sử cố định \(r\) và một hoán vị \(v_0,v_1,\ldots,v_{|T(r)|-1}\) của các đỉnh trong \(T(r)\). Với mỗi \(i\) thỏa mãn \(1\le i<|T(r)|\), gọi \(f(i)\) là số lần màu \(C[v_i]\) xuất hiện trong dãy \(i-1\) màu \(C[v_1],C[v_2],\ldots,C[v_{i-1}]\).

Lưu ý rằng \(f(1)\) luôn bằng \(0\) vì dãy màu trong định nghĩa là rỗng.

Hoán vị \(v_0,v_1,\ldots,v_{|T(r)|-1}\) là hoán vị đẹp khi và chỉ khi thỏa mãn tất cả các tính chất sau:

• \(v_0=r\).
• Với mỗi \(i\) thỏa mãn \(1\le i<|T(r)|\), cha của đỉnh \(v_i\) là đỉnh \(v_{f(i)}\).

Với mỗi \(r\) thỏa mãn \(0\le r<N\), cây con \(T(r)\) là cây con đẹp khi và chỉ khi tồn tại một hoán vị đẹp của các đỉnh trong \(T(r)\). Theo định nghĩa này, mọi cây con chỉ có một đỉnh đều đẹp.

Xét cây ví dụ ở trên. Có thể chứng minh \(T(0)\) và \(T(3)\) không đẹp. Cây con \(T(14)\) đẹp vì chỉ có một đỉnh. Dưới đây, ta sẽ chứng minh \(T(1)\) cũng đẹp.

Xét dãy số nguyên khác nhau \([v_0,v_1,v_2,v_3,v_4,v_5,v_6]=[1,4,5,12,13,6,14]\). Đây là một hoán vị của các đỉnh trong \(T(1)\). Hình sau mô tả hoán vị này; nhãn gắn với mỗi đỉnh là chỉ số mà đỉnh đó xuất hiện trong hoán vị.

Ta kiểm tra đây là một hoán vị đẹp:

• \(v_0=1\).
• \(f(1)=0\) vì \(C[v_1]=C[4]=1\) xuất hiện \(0\) lần trong dãy \([]\). Tương ứng, cha của \(v_1\) là \(v_0\): cha của đỉnh \(4\) là đỉnh \(1\), tức \(P[4]=1\).
• \(f(2)=0\) vì \(C[v_2]=C[5]=2\) xuất hiện \(0\) lần trong dãy \([1]\). Tương ứng, cha của \(v_2\) là \(v_0\): cha của đỉnh \(5\) là đỉnh \(1\).
• \(f(3)=1\) vì \(C[v_3]=C[12]=1\) xuất hiện \(1\) lần trong dãy \([1,2]\). Tương ứng, cha của \(v_3\) là \(v_1\): cha của đỉnh \(12\) là đỉnh \(4\).
• \(f(4)=1\) vì \(C[v_4]=C[13]=2\) xuất hiện \(1\) lần trong dãy \([1,2,1]\). Tương ứng, cha của \(v_4\) là \(v_1\): cha của đỉnh \(13\) là đỉnh \(4\).
• \(f(5)=0\) vì \(C[v_5]=C[6]=3\) xuất hiện \(0\) lần trong dãy \([1,2,1,2]\). Tương ứng, cha của \(v_5\) là \(v_0\): cha của đỉnh \(6\) là đỉnh \(1\).
• \(f(6)=2\) vì \(C[v_6]=C[14]=2\) xuất hiện \(2\) lần trong dãy \([1,2,1,2,3]\). Tương ứng, cha của \(v_6\) là \(v_2\): cha của đỉnh \(14\) là đỉnh \(5\).

Vì tìm được một hoán vị đẹp của các đỉnh trong \(T(1)\), cây con \(T(1)\) là cây con đẹp.

Nhiệm vụ của bạn là giúp Árpád xác định với mỗi cây con của cây Ős Vezér, cây con đó có đẹp hay không.

Chi tiết cài đặt

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

std::vector<int> beechtree(
    int N, int M, std::vector<int> P, std::vector<int> C);

• \(N\): số đỉnh của cây.
• \(M\): số màu có thể có của các cạnh.
• \(P,C\): các mảng độ dài \(N\) mô tả các cạnh của cây.
• Hàm cần trả về mảng \(b\) có độ dài \(N\). Với mỗi \(r\) thỏa mãn \(0\le r<N\), \(b[r]=1\) nếu \(T(r)\) đẹp, và \(b[r]=0\) nếu ngược lại.
• Hàm được gọi đúng một lần cho mỗi test.

Các ví dụ

Ví dụ 1

Xét lời gọi sau:

beechtree(4, 2, [-1, 0, 0, 0], [0, 1, 1, 2])

Cây tương ứng được mô tả trong hình sau:

\(T(1)\), \(T(2)\) và \(T(3)\) mỗi cây chỉ có một đỉnh nên đều đẹp. \(T(0)\) không đẹp. Vì vậy, hàm cần trả về \([0,1,1,1]\).

Ví dụ 2

Xét lời gọi sau:

beechtree(18, 3,
          [-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11],
          [0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3])

Ví dụ này được minh họa trong phần mô tả bài toán ở trên. Hàm cần trả về \([0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]\).

Ví dụ 3

Xét lời gọi sau:

beechtree(7, 2, [-1, 0, 1, 1, 0, 4, 5], [0, 1, 1, 2, 2, 1, 1])

Ví dụ này được minh họa trong hình sau:

\(T(0)\) là cây con duy nhất không đẹp. Hàm cần trả về \([0,1,1,1,1,1,1]\).

Các ràng buộc

• \(3\le N\le 200\,000\).
• \(2\le M\le 200\,000\).
• \(0\le P[i]<i\) với mỗi \(i\) thỏa mãn \(1\le i<N\).
• \(1\le C[i]\le M\) với mỗi \(i\) thỏa mãn \(1\le i<N\).
• \(P[0]=-1\) và \(C[0]=0\).

Các subtask

Trình chấm mẫu

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

dòng 1: N M
dòng 2: P[0] P[1] … P[N − 1]
dòng 3: C[0] C[1] … C[N − 1]

Gọi \(b[0],b[1],\ldots\) là các phần tử của mảng do beechtree trả về. Trình chấm mẫu in câu trả lời trên một dòng theo định dạng sau:

dòng 1: b[0] b[1] …

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.