Black And White Trees

Black And White Tree

Bir tahtaya ağaç şeklinde bir graf çizilmiştir. Bildiğiniz gibi bağlı döngü olmayan ve yönsüz graflara ağaç denmektedir. Bu ağaçtaki her düğümün siyah ya da beyaz olmak üzere bir rengi vardır. Ağacın kenarları yalnızca farklı renkteki değerleri bağlar ve her kenarın bir değeri vardır.

Daha sonra Vasya adındaki kötü bir çocuk gelir ve her düğümün yanına o düğüme giren kenarların değerleri toplamını yazar. Sonra da bütün kenarları ve kenarların değerlerini siler.

Düğümlerin renkleri ve giren kenarların değerleri toplamı size verildiğinde orijinal ağacı bulan bir program yazınız.

Girdi

Girdinin ilk satırına düğüm sayısı N (2 ≤ N ≤ 100.000) verilecektir. Ardından gelen N satırda; i+1. satırda i. düğüm için birer boşlukla ayrılmış C_i ve S_i verilecektir. ( 0 ≤ C_i ≤ 1 , 0 ≤ S_i ≤ 10⁹).

C_i = 0 ise beyaz, 1 ise düğüm siyahtır. V_i , U_i , W_i ( 1 ≤ V_i , U_i ≤ N ,  V_i ≠ U_i , 0 ≤ W_i ≤ 10⁹). V_i ve U_i düğümleri arasına W_i değerinde kenar olduğu anlamına gelmektedir. Hiçbir düğümden kendisine yol olmayacağına dikkat ediniz. Her girdi için uygun bir çözüm olacağı garanti edilmektedir. Birden fazla çözüm varsa kenarları istediğiniz sırada yazdırabilirsiniz.

Çıktı

Çıktıya N-1 satırda kenarları yazdırmanız istenmektedir. Her kenarı 3 adet tamsayı ile göstermelisiniz. V_i , U_i , W_i ( 1 ≤ V_i , U_i ≤ N ,  V_i ≠ U_i , 0 ≤ W_i ≤ 10⁹). V_i ve U_i düğümleri arasına W_i değerinde kenar olduğu anlamına gelmektedir. Hiçbir düğümden kendisine yol olmayacağına dikkat ediniz. Her girdi için uygun bir çözüm olacağı garanti edilmektedir. Birden fazla çözüm varsa kenarları istediğiniz sırada yazdırabilirsiniz.

Örnek girdi

3
1 3
1 2
0 5

Örnek çıktı

3 1 3
3 2 2

Sorunun linki:  http://codeforces.com/contest/260/problem/D

İngilizce analiz için link:  http://codeforces.com/blog/entry/6263

Çözüm

Bu problemi çözmek için yapılması gereken asıl gözlem Siyah ve Beyaz düğümlerin değerlerinin toplamının aynı olmasıdır. Ağaç bipartite bi graf olduğundan biz de problemdeki şartları sağlayan siyah ve beyaz düğümlerden oluşan bipartite bir oluşturacağız. Her adımda siyah ve beyaz düğümlerden minimum değerli bir A düğümü seçeriz  ve karşı renk olan ve değeri A’nınkinden büyük herhangi bir B düğümü ile arasına A’nın değeri değerinde bir kenar ekleriz. B’nin değerinden  A’nın değerini çıkarıp ve A düğümünü listeden çıkarıp aynı işlemleri tekrar yaparız, bu şekilde her kenar eklediğimizde bir düğüm silinir ve asla döngü oluşmaz ve N-1 adet yol eklediğimizden şartları sağlayan bir ağaç oluşmuş olur.