Kavak

Soru Metni

        Enes Kavak eski bir bilgisayar olimpiyatcisidir. Eskiden sorulara cok iyi cozum bulabildigi halde,buglar ve kod yazamama gibi problemler yuzunden basarili bir olimpiyat gecmisi olmasa da hala eski olimpiyat sorulariyla ugrasmayi ve olimpiyat sorulari yazmayi sevmektedir. Yusuf Hakan Enes’ten yaz kampi sonu sinavi icin soru hazirlamasini istemistir ve Enes sorulara hikaye yazma konusunda kod yazmasina kiyasla bile basarili sayilamiyacagini bilmektedir. Bundan dolayi, Enes soruya hikaye uyduracagina direk soruyu yazmayi tercih etmistir:

        Size N lik bir agac verildiginde, sizden istenen kendisine en uzak node ile en yakin yaprak – hicbir node’un atasi olmayan node’lara yaprak denir - arasindaki mesafe farki minimum olan node icin bu farki ciktiya bastirmaniz.

Girdi Biçimi
        Ilk satirda N’I belirten tek bir sayi.
        2…N. satirda her satirda i. node’un atasini ve atasiyla arasindaki mesafeyi belirten iki adet sayi

Çıktı Biçimi
        Kendisine en uzak node ile en yakin node arasindaki mesafe farki minimum olan node icin bu
farki belirten sayi.

Örnek Girdi 1
3
1 2
2 2
Örnek Çıktı 1
0

Örnek Girdi 2
5
1 1
1 2
2 3
3 4

Örnek Çıktı 2

2

-----------------------------------------------------------------------------------------------------------------------------------------

Çözüm Metni

Subtask 1

Verilen sınırlar için çözüm gayet basittir. Sırasıyla bir merkez node bir en yakın yaprak node bir de en uzak node'u belirten 3 farklı node seçip tüm durumlara bakıldıktan sonra bütün durumlar içinde en yakın yaprak node ve en uzak node'un merkez node'a uzaklıkları farkının minimum olduğu durum bize asıl çözümü verecektir. Zaman karmaşıklığı: O(N³) olur.

Subtask 2

Her bir node'u tek tek merkez node kabul edip ona en uzak olan node'u ve ona en yakın olan yaprak node'u bulabiliriz. Bulduğumuz bu iki node'un seçilen merkeze uzaklığı belirlenen merkez için çözüm olmaktadır. Bütün merkez seçimleri içerisinde minimum değere sahip olanı cevap olacaktır.

Merkez node seçildiğinde en yakın yaprak ve en uzak node nasıl bulunur: Bu sorunun cevabı gayet kolaydır. Merkez node'tan dfs işlemi uygulanarak varılan yaprak node'lar arasında uzaklığı minimum olan alınır ve gezilen tüm node'lar arasında uzaklığı maksimum olan alınır. Bu şekilde aranan değerleri bulabiliriz.

Zaman karmaşıklığı: O(N) işlemde merkez node seçilir. O(N) işlemde en yakın yaprak ve en uzak node bulunur. Total: O(N²) olur.

Subtask 3

Sorunun asıl çözümü için her node'u tek tek merkez node kabul edip ona en uzak olan node'u ve en yakın yaprak node'u bulacağız. Ancak bunu yaparken az önce gösterdiğimiz çözümden daha iyi bir çözüm geliştirmeliyiz. Örneğin X node'u merkez node olarak seçilmiş olsun ve P node'u X node'unun

atası olsun. Bizim X node'una en uzak node'u ve ona en yakın olan yaprak node'unu bulmamız gerekmektedir.
Bunları şu şekilde bulabiliriz: Her bir node kendi altındaki kendine en uzak node'un uzaklığını ve kendine en yakın yaprağın uzaklığını tutmalıdır. Bunu tek dfs ile O(N) işlemde yapabiliriz. Eğer ki X node'unu merkez olarak değerlendirmek istiyorsak X e en uzak node'un uzaklığı ya X'in altındaki X'e en uzak olanın uzaklığıdır ya da X in altında olmayıp P ye en uzak olanın uzaklığı + L dir. Aynı şekilde X e en yakın yaprağın uzaklığı ya X in altında X e en yakın yaprağın uzaklığıdır ya da X in altında olmayan P ye en yakın yaprağın uzaklığı + L dir.

Yukarıda anlatılan işlemi gerçekleştirmek için ilk başta her bir node için kendi altındaki en uzak ve en yakın yaprak node'un uzaklıkları bulunduktan sonra root'tan başlayarak tüm node'ları ayrı ayrı merkez olarak değerlendireceğiz. Bunu yine O(N) lik tek dfs ile yapacağız. Her node'a kendi atasından gelmesi gereken veriler gelecek yani(X için X in altında bulunmayan P ye en yakın yaprağın uzaklığı + L ve X in altında bulunmayan P ye en uzak node'un uzaklığı + L) ve bu gelenler ile X in altında bulunanlar kıyaslanarak X e en yakın yaprağın uzaklığı ve en uzak node'un uzaklığı bulunabilir. Bu da X merkez olduğunda cevap olur.

Bir node'a üzerinden gerekli verilerin gelmesi:
X için ele alırsak, P eğer kendi altındak en uzak node'un ve en uzak ikinci node'un uzaklığını tutarsa aynı zamanda en yakın ve en yakın ikinci yaprağın uzaklığını tutarsa, X gibi bir çocuğa dfs ile dallanırken sadece bu 4 değer ile istenen verileri sağlar.
   - Eğer P ye en uzak node X in altından geliyorsa gönderilecek en uzak değeri ikinci en uzak olan ya da K dan gelen en uzak değeridir.
   - Eğer P ye en uzak node X in altından gelmiyorsa gönderilecek en uzak değeri ilk en uzak olan ya da K dan gelen en uzak değeridir.
   - Eğer P ye en yakın yaprak X in altından geliyorsa gönderilecek en yakın değeri ikinci en yakın olan ya da K dan gelen en yakın değeridir.
   - Eğer P ye en yakın yaprak X in altından gelmiyorsa gönderilecek en yakın değeri ilk en yakın olan ya da K dan gelen en yakın değeridir.

Çözüm Kodu(kopyalayıp başka bir yerde baksanız daha iyi olur sanırım)
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#define MAXN 500010
#define fi first
#define se second
using namespace std;
typedef pair<int, int> ii;

int N;
vector<ii> Way[MAXN];
int Dn[MAXN][2];

void f(int k, int dad){
Dn[k][0] = -1;
Dn[k][1] = -1;

for(int i = 0, mi = Way[k].size(); i < mi; i++)
if(Way[k][i].fi != dad){
f(Way[k][i].fi, k);

if(Dn[k][0] == -1 || Dn[k][0] < Dn[Way[k][i].fi][0] + Way[k][i].se)
Dn[k][0] = Dn[Way[k][i].fi][0] + Way[k][i].se;
if(Dn[k][1] == -1 || Dn[k][1] > Dn[Way[k][i].fi][1] + Way[k][i].se)
Dn[k][1] = Dn[Way[k][i].fi][1] + Way[k][i].se;
}

if(dad == 0 && Way[k].size() == 1)
Dn[k][1] = 0;

if(Dn[k][0] == -1)
Dn[k][0] = 0;
if(Dn[k][1] == -1)
Dn[k][1] = 0;
}

void f2(int k, int dad, int maxDistance, int minDistance){
if(maxDistance != -1 && Dn[k][0] < maxDistance)
Dn[k][0] = maxDistance;
if(minDistance != -1 && Dn[k][1] > minDistance)
Dn[k][1] = minDistance;

int tempMax = -1, maxNode;
int tempMax2 = -1, maxNode2;
int tempMin = -1, minNode; 
int tempMin2 = -1, minNode2;

if(maxDistance == -1)
maxDistance = 0;
if(minDistance == -1 && Way[k].size() == 1)
minDistance = 0;

for(int i = 0, mi = Way[k].size(); i < mi; i++)
if(Way[k][i].fi != dad){
if(tempMax == -1 || Dn[Way[k][i].fi][0] + Way[k][i].se > tempMax){
tempMax2 = tempMax;
maxNode2 = maxNode;
tempMax = Dn[Way[k][i].fi][0] + Way[k][i].se;
maxNode = Way[k][i].fi;
}
else if(tempMax2 == -1 || Dn[Way[k][i].fi][0] + Way[k][i].se > tempMax2){
tempMax2 = Dn[Way[k][i].fi][0] + Way[k][i].se;
maxNode2 = Way[k][i].fi;
}

if(tempMin == -1 || tempMin > Dn[Way[k][i].fi][1] + Way[k][i].se){
tempMin2 = tempMin;
minNode2 = minNode;
tempMin = Dn[Way[k][i].fi][1] + Way[k][i].se;
minNode = Way[k][i].fi;
}
else if(tempMin2 == -1 || tempMin2 > Dn[Way[k][i].fi][1] + Way[k][i].se){
tempMin2 = Dn[Way[k][i].fi][1] + Way[k][i].se;
minNode2 = Way[k][i].fi;
}
}

int tmpMax, tmpMin;
for(int i = 0, mi = Way[k].size(); i < mi; i++)
if(Way[k][i].fi != dad){
tmpMax = maxDistance;
tmpMin = minDistance;
if(Way[k][i].fi == maxNode && tempMax2 != -1 && (maxDistance == -1 || tempMax2 > maxDistance))
tmpMax = tempMax2;
else if(Way[k][i].fi != maxNode && tempMax != -1 && (maxDistance == -1 || tempMax > maxDistance))
tmpMax = tempMax;

if(Way[k][i].fi == minNode && tempMin2 != -1 && (minDistance == -1 || tempMin2 < minDistance))
tmpMin = tempMin2;
else if(Way[k][i].fi != minNode && tempMin != -1 && (minDistance == -1 || tempMin < minDistance))
tmpMin = tempMin;

if(tmpMin != -1)
tmpMin += Way[k][i].se;
if(tmpMax != -1)
tmpMax += Way[k][i].se;
f2(Way[k][i].fi, k, tmpMax, tmpMin);
}
}

int main(){
scanf("%d", &N);

for(int i = 2, a, b; i <= N; i++){
scanf("%d %d", &a, &b);
Way[i].push_back(ii(a, b));
Way[a].push_back(ii(i, b));
}

f(1, 0);
f2(1, 0, -1, -1);

int rev = -1;
for(int i = 1; i <= N; i++)
if(rev == -1 || Dn[i][0] - Dn[i][1] < rev)
rev = Dn[i][0] - Dn[i][1];

printf("%d\n", rev);

return 0;
}