Saat iseng mencari soal di SPOJ, tiba-tiba saya mendapatkan soal yang menarik. Soal itu adalah SPOJ - MTREE. Terlihat mudah, tetapi tidak begitu. Oleh sebab itu saya akan membahasnya. Saya juga menyarankan Anda untuk mencoba mengerjakan soal itu terlebih dahulu.
Cara paling sederhana adalah dengan mencoba semua N2 kemungkinan path, lalu mengalikan keseluruhannya dalam O(N). Sehingga kompleksitas akhirnya O(N3) dan jelas TLE. Cara yang lebih cepat adalah mengalikan sambil mencoba semua kemungkinan jalur, sehingga kompleksitasnya O(N2). Cara ini juga jelas TLE.
Untuk ide menyelesaikannya, mari sederhanakan persoalannya terlebih dahulu. Misalkan tree yang diberikan adalah binary tree yang memiliki root (rooted binary tree), dan kita tertarik untuk mencari bobotnya (sesuai dengan deskripsi soal).
Perhatikan gambar berikut untuk penjelasan di bagian-bagian berikutnya:
Cara paling sederhana adalah dengan mencoba semua N2 kemungkinan path, lalu mengalikan keseluruhannya dalam O(N). Sehingga kompleksitas akhirnya O(N3) dan jelas TLE. Cara yang lebih cepat adalah mengalikan sambil mencoba semua kemungkinan jalur, sehingga kompleksitasnya O(N2). Cara ini juga jelas TLE.
Untuk ide menyelesaikannya, mari sederhanakan persoalannya terlebih dahulu. Misalkan tree yang diberikan adalah binary tree yang memiliki root (rooted binary tree), dan kita tertarik untuk mencari bobotnya (sesuai dengan deskripsi soal).
Perhatikan gambar berikut untuk penjelasan di bagian-bagian berikutnya:
