2872. Bilangan Maksimum Komponen K-Divisible

Kesukaran: Sukar

Topik: Pokok, Carian Pertama Kedalaman

Terdapat pepohon tidak berarah dengan n nod dilabelkan daripada 0 hingga n - 1. Anda diberi integer n dan integer array integer tepi panjang - 1, dengan tepi[i] = [a_i, b_i] menunjukkan bahawa terdapat tepi antara nod a_i dan b_i di dalam pokok.

Anda juga diberi 0-diindeks nilai tatasusunan integer dengan panjang n, dengan nilai[i] ialah nilai yang dikaitkan dengan nod i^th dan integer k.

Satu Pecahan sah pokok diperoleh dengan mengalih keluar sebarang set tepi, mungkin kosong, daripada pokok supaya komponen yang terhasil semuanya mempunyai nilai yang boleh dibahagikan dengan k, di mana nilai bagi komponen yang disambungkan ialah jumlah nilai nodnya.

Kembalikan bilangan maksimum komponen dalam mana-mana pembahagian yang sah.

Contoh 1:

• Input: n = 5, tepi = [[0,2],[1,2],[1,3],[2,4]], nilai = [1,8,1,4 ,4], k = 6
• Output: 2
• Penjelasan: Kami mengeluarkan tepi menyambungkan nod 1 dengan 2. Pemisahan yang terhasil adalah sah kerana:
  • Nilai komponen yang mengandungi nod 1 dan 3 ialah nilai[1] nilai[3] = 12.
  • Nilai komponen yang mengandungi nod 0, 2 dan 4 ialah nilai[0] nilai[2] nilai[4] = 6.
  • Ia boleh ditunjukkan bahawa tiada pemisahan sah lain yang mempunyai lebih daripada 2 komponen bersambung.

Contoh 2:

• Input: n = 7, tepi = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6] ], nilai = [3,0,6,1,5,2,1], k = 3
• Output: 3
• Penjelasan: Kami mengeluarkan nod penghubung tepi 0 dengan 2, dan nod penghubung tepi 0 dengan 1. Pemisahan yang terhasil adalah sah kerana:
  • Nilai komponen yang mengandungi nod 0 ialah nilai[0] = 3.
  • Nilai komponen yang mengandungi nod 2, 5 dan 6 ialah nilai[2] nilai[5] nilai[6] = 9.
  • Nilai komponen yang mengandungi nod 1, 3 dan 4 ialah nilai[1] nilai[3] nilai[4] = 6.
  • Ia boleh ditunjukkan bahawa tiada pemisahan sah lain yang mempunyai lebih daripada 3 komponen bersambung.

Kekangan:

• 1 <= n <= 3 * 10⁴
• tepi.panjang == n - 1
• tepi[i].panjang == 2
• 0 <= ai, bi < n
• nilai.panjang == n
• 0 <= nilai[i] <= 10⁹
• 1 <= k <= 10⁹
• Jumlah nilai boleh dibahagi dengan k.
• Input dijana sedemikian rupa sehingga tepi mewakili pokok yang sah.

Petunjuk:

1. Akar pokok pada nod 0.
2. Jika nod daun tidak boleh dibahagikan dengan k, ia mesti berada dalam komponen yang sama dengan nod induknya supaya kami menggabungkannya dengan nod induknya.
3. Jika nod daun boleh dibahagikan dengan k, ia akan berada dalam komponennya sendiri jadi kami memisahkannya daripada nod induknya.
4. Dalam setiap langkah, kita sama ada memotong nod daun ke bawah atau menggabungkan nod daun. Bilangan nod pada pokok berkurangan satu. Ulangi proses ini sehingga hanya satu nod yang tinggal.

Penyelesaian:

Kami boleh melaksanakan pendekatan Depth-First Search (DFS) untuk meneroka pepohon, menjejaki nilai komponen dan mencari bilangan maksimum pemisahan yang sah.

Perkara Utama:

• Struktur Pokok: Kami sedang bekerja dengan pokok tidak terarah di mana setiap nod mempunyai nilai yang berkaitan. Kita perlu mencari bilangan maksimum komponen yang disambungkan yang boleh kita perolehi dengan membelah pokok supaya jumlah nilai setiap komponen boleh dibahagikan dengan k.
• DFS Traversal: Kami menggunakan Depth-First Search (DFS) untuk melintasi pokok dan mengira jumlah subpokok.
• Semakan Kebolehbahagiaan: Selepas mengira jumlah subpokok, jika ia boleh dibahagi dengan k, ini bermakna subpokok boleh dianggap sebagai komponen yang sah dengan sendirinya.
• Penyingkiran Tepi: Dengan mengalih keluar tepi yang menyambungkan nod yang jumlah subpokoknya tidak boleh dibahagikan dengan k, kita boleh memaksimumkan bilangan komponen yang sah.

Pendekatan:

1. Perwakilan Pokok: Tukar senarai tepi kepada senarai bersebelahan untuk mewakili pokok.
2. DFS Traversal: Mulakan dari nod 0 dan hitung secara rekursif jumlah nilai dalam setiap subpokok. Jika jumlahnya boleh dibahagi dengan k, kita boleh memotong subpokok itu daripada induknya, dengan berkesan membentuk komponen yang sah.
3. Pengiraan Global: Kekalkan pembilang global (hasil) yang menjejaki bilangan komponen sah yang dibentuk oleh bahagian canggih.
4. Semakan Akhir: Pada penghujung traversal DFS, pastikan bahawa jika jumlah jumlah subpokok punca boleh dibahagi dengan k, ia dikira sebagai komponen yang sah.

Pelan:

1. Penghuraian Input: Tukar input ke dalam bentuk yang boleh digunakan. Khususnya, buat perwakilan senarai bersebelahan untuk pokok itu.
2. Fungsi DFS: Tulis fungsi rekursif dfs(nod) yang mengira jumlah nilai dalam subpokok yang berakar pada nod. Jika jumlah ini boleh dibahagi dengan k, naikkan pembilang hasil dan "potong" tepi dengan mengembalikan 0 untuk mengelakkan bergabung kembali ke dalam induk.
3. Mulakan DFS dari Root: Panggil dfs(0) dan kemudian semak nilai akhir hasil.

Langkah Penyelesaian:

1. Bina Pokok: Tukar senarai tepi kepada senarai bersebelahan untuk laluan yang lebih mudah.
2. Memulakan Tatasusunan Dilawati: Gunakan tatasusunan yang dilawati untuk memastikan kami tidak melawati semula nod.
3. DFS Traversal: Lakukan DFS bermula dari nod 0. Untuk setiap nod, hitung jumlah nilai subpokoknya.
4. Semak Kebolehbahagiaan: Jika jumlah subpokok boleh dibahagi dengan k, naikkan hasilnya dan tetapkan semula jumlah subpokok kepada 0.
5. Semakan Komponen Akhir: Selepas traversal DFS, periksa sama ada keseluruhan pokok (berakar pada nod 0) mempunyai jumlah yang boleh dibahagikan dengan k dan kirakan ia sebagai komponen berasingan jika perlu.

Mari kita laksanakan penyelesaian ini dalam PHP: 2872. Bilangan Maksimum Komponen K-Divisible

  
  
  Penjelasan:




Pembinaan Pokok: Kami membina senarai bersebelahan untuk mewakili struktur pokok. Setiap tepi menghubungkan dua nod dan kami menggunakan senarai bersebelahan ini untuk melintasi pokok.

DFS Traversal: Fungsi DFS secara rekursif mengira jumlah subpokok yang berakar pada setiap nod. Jika jumlah subpokok boleh dibahagi dengan k, kami menambah hasilnya dan menganggap subpokok sebagai komponen sah yang berasingan.

Mengembalikan Jumlah Subtree: Untuk setiap nod, fungsi DFS mengembalikan jumlah nilai untuk subtreenya. Jika subpokok boleh dibahagi dengan k, kita secara berkesan "memotong" tepi dengan mengembalikan jumlah 0, menghalang penggabungan selanjutnya dengan nod induk.

Semakan Akhir: Pada penghujung DFS, kami memastikan bahawa jika jumlah keseluruhan pokok boleh dibahagi dengan k, ia dikira sebagai komponen yang sah.



  
  
  Contoh Panduan:


Contoh 1:

Input:



n = 5, tepi = [[0,2],[1,2],[1,3],[2,4]], nilai = [1,8,1,4,4], k = 6. 


DFS bermula dari nod 0:


Nod 0: jumlah subpokok = 1
Nod 2: jumlah subpokok = 1 1 4 = 6 (boleh bahagi dengan 6, jadi kita boleh memotong tepi ini)
Nod 1: jumlah subpokok = 8 4 = 12 (boleh bahagi dengan 6, potong tepi ini)
Bilangan akhir komponen = 2.


Contoh 2:

Input:



n = 7, tepi = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], nilai = [3,0 ,6,1,5,2,1], k = 3.


DFS bermula dari nod 0:


Nod 0: jumlah subpokok = 3
Nod 2: jumlah subpokok = 6 2 1 = 9 (boleh bahagi dengan 3, potong tepi ini)
Nod 1: jumlah subpokok = 0 5 = 5 (tidak boleh dibahagikan dengan 3, gabungkan jumlah ini)
Bilangan akhir komponen = 3.



  
  
  Kerumitan Masa:




Kerumitan Masa DFS: O(n), dengan n ialah bilangan nod. Kami melawati setiap nod sekali dan melaksanakan operasi masa tetap pada setiap nod.

Kerumitan Ruang: O(n) untuk senarai bersebelahan, tatasusunan yang dilawati dan timbunan ulangan.


Oleh itu, kerumitan masa dan ruang keseluruhan ialah O(n), menjadikan pendekatan ini cekap untuk kekangan masalah yang diberikan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Bilangan Maksimum Komponen K-Divisible. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!