Đề bài

Cho một cây có gốc gồm \(N\) đỉnh, đánh số từ \(0\) đến \(N-1\), với gốc là đỉnh \(0\). Mỗi đỉnh có đúng \(0\) hoặc \(2\) con; nếu có hai con thì thứ tự con trái và con phải được xác định. Mỗi cạnh \(e\) có độ dài nguyên dương \(c_e\).

Ta cần vẽ cây trên mặt phẳng tọa độ. Mỗi đỉnh \(v\) được đặt tại một điểm lưới nguyên phân biệt \(m_v=(x_v,y_v)\), trong đó \(m_0=(0,0)\).

Cạnh \(e=(p,v)\) được vẽ thành một đường đi từ \(m_p\) đến \(m_v\) thỏa mãn:

• Khi đi từ \(m_p\) đến \(m_v\), mỗi đoạn luôn đi theo hướng tăng \(x\) hoặc tăng \(y\), không đi chéo. Chỉ được đổi hướng tại điểm lưới nguyên; một đường đi dài \(k\) chỉ có thể đổi hướng tại \(k-1\) điểm trung gian.
• Nếu \(v\) là con trái của \(p\), đoạn đầu tiên đi theo hướng tăng \(x\).
• Nếu \(v\) là con phải của \(p\), đoạn đầu tiên đi theo hướng tăng \(y\).
• Độ dài đường đi không nhỏ hơn \(c_e\).
• Các đường đi không được cắt nhau: không điểm trong nào của một đường đi được thuộc một đường đi khác. Điểm đầu và cuối không được tính là điểm trong.

Độ sâu của đỉnh \(v\) trong hình vẽ được định nghĩa là

Tất cả các lá phải có cùng độ sâu; giá trị chung này gọi là độ sâu lưới. Hãy tìm độ sâu lưới nhỏ nhất trong mọi hình vẽ hợp lệ.

Yêu cầu cài đặt

long long compute_min_depth(
    int N,
    vector<int> P,
    vector<int> C,
    vector<int> D
);

Với mỗi \(1\le i\le N-1\):

• cha của đỉnh \(i\) là P[i-1];
• cạnh nối chúng có độ dài C[i-1];
• D[i-1]=0 nếu \(i\) là con trái, và D[i-1]=1 nếu \(i\) là con phải.

Luôn tồn tại ít nhất một hình vẽ hợp lệ. Hàm phải trả về độ sâu lưới nhỏ nhất, được gọi đúng một lần, và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• Các cạnh tạo thành một cây gốc tại đỉnh \(0\).
• Mỗi đỉnh có \(0\) hoặc \(2\) con.
• \(3\le N\le 200\,000\).
• \(0\le P[i]\le N-1\).
• \(1\le C[i]\le 10^9\).
• \(D[i]\in\{0,1\}\).

Khoảng cách giữa hai đỉnh của cây là tổng độ dài các cạnh trên đường đi duy nhất nối chúng.

Phân nhóm

Trong nhóm 3, nếu không tồn tại hình vẽ có độ sâu lưới đúng bằng \(K\), hàm được phép trả về \(-1\) thay cho độ sâu lưới nhỏ nhất. Cụ thể:

• Nếu tồn tại hình vẽ có độ sâu \(K\), chỉ giá trị \(K\) được chấp nhận.
• Nếu không tồn tại hình vẽ có độ sâu \(K\), cả giá trị nhỏ nhất thực sự và \(-1\) đều được chấp nhận.

Grader mẫu

Grader mẫu đọc \(N\), sau đó đọc \(N-1\) dòng P[i] C[i] D[i], và in giá trị trả về.

5
4 1 0
0 2 1
4 1 1
0 1 0

2

9
0 2 0
0 1 1
1 1 0
1 1 1
2 1 0
2 1 1
5 1 0
5 1 1

4

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 1, giấy phép CC BY-NC-SA 4.0.