Ağac

Verilmiş asılmış ağacda, düyünlərdə tam ədədlər yerləşdirilib. Hər bir daxili düyün üçün, alt ağacın iki müxtəlif zirvəsindəki ədədlərin fərqinin minimal modulunu tapmaq tələb olunur.

Giriş məlumatları

Birinci sətirdə ağacın zirvələrinin sayı n (1 ≤ n ≤ 40000) verilir. Sonrakı n sətirdə p[i] və v[i] ədədləri (0 ≤ i < n) cütləri təqdim olunur. Burada p[i] — i nömrəli zirvənin əcdadının nömrəsidir. Əgər p[i] = -1 olarsa, bu zirvə kök olur. v[i] — zirvədə yerləşdirilmiş ədəd (0 ≤ v[i] ≤ 10^6).

Çıxış məlumatları

Yeganə ədəd çıxarın

modul P ilə. Burada i daxili zirvələrin indekslərinin çoxluğunu, a[i] isə onlar üçün cavabları ifadə edir (q = 127, P = 1000000007).

Nümunələr