Z02
En Uzun Mesai Zinciri
Teknik Tanım & Görev
Bir enerji şirketi n adet trafo merkezini, iki yönlü iletim hatlarıyla birbirine bağlıyor. Hat listesi [a, b, uzunluk] üçlüleriyle veriliyor ve şebeke bir AĞAÇ oluşturuyor (n düğüm, n-1 hat, tam bağlı, döngü yok).
Şirket, yıllık bakım turu için ŞEBEKEDEKİ EN UZUN BASİT ROTAYI çıkarmak istiyor: bir trafo merkezinden başlayıp başka bir trafo merkezinde biten, hiçbir hattı İKİ KEZ kullanmayan ve TOPLAM HAT UZUNLUĞU EN BÜYÜK olan rota.
Bu en uzun rotanın toplam uzunluğunu döndür.
n büyük bir ağaçta özyinelemeli çap hesabı çağrı sınırını aşabilir. İki DFS turunu açık yığınla veya sınırı yükselterek uygulayın.
Fonksiyon İmzası (Python)
en_uzun_zincir(n: int, hatlar: list[list[int]]) -> intGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:En uzun basit yolun toplam ağırlığı. n <= 1 ise 0.
Sistem Kısıtları (Constraints)
1 <= n <= 10^5
hatlar.length == n - 1 (n=1 ise boş)
1 <= uzunluk <= 10^4
Girdi her zaman geçerli bir bağlı ağaçtır.Örnek Yürütme Analizi
n = 4, hatlar = [[0,1,3], [1,2,4], [2,3,5]]
şebeke: 0 --3-- 1 --4-- 2 --5-- 3
en uzun rota: 0 -> 3, uzunluk 3 + 4 + 5 = 12
cevap: 12Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[4,[[0,1,3],[1,2,4],[2,3,5]]]Beklenen Çıktı:
12Örnek 2: 3 Düğüm Doğrusal Hat (15)
Girdi:
[3,[[0,1,5],[1,2,10]]]Beklenen Çıktı:
15Örnek 3: V Şekilli Hat (10)
Girdi:
[3,[[0,1,4],[0,2,6]]]Beklenen Çıktı:
10