Editorial Codeforces 1540B

Tree Array

Deskripsi Singkat

Diberikan tree ukuran $N$.

• Pilih secara random $1$ node secara uniform, dan beri tanda.
• Pilih secara random $1$ node secara uniform dari nodes yang memiliki node ke node yang sudah diberi tanda, kemudian tandai node tersebut.

Akan didapatkan sebuah permutasi urutan pemberian nodes. Tentukan expected value dari banyaknya inversion.

Contoh Masukan

3
1 2
1 3

Contoh Keluaran

166666669

Solusi

Pertama kita bisa observasi, bahwa solusinya akan dihitung terpisah untuk setiap node $R$ saat node $R$ ini menjadi root. Selanjutnya kita observasi lagi, bahwa expected value dari sebuah inversion itu independen, jadi kita bisa saja mencari untuk setiap pasang $i, j$ berapa kemungkinan node $i$ akan dipanggil duluan dari node $j$ jika kepala rootnya $R$.

Selanjutnya, kita bisa cari observasi tambahan, bahwa katakan sebuah fungsi $cnt(x)$ ialah banyaknya permutasi yang bisa dihasilkan bila node $x$ menjadi root saat ini. Bisa kita dapat sebuah rumus rekursi. Kita definisikan juga fungsi $size(x)$ sebagai ukuran subtree dari sebuah node $x$. Kita defiisikan $Child(x)$ ialah set dari semua anak $x$. \(cnt(x) = \binom{\sum{size(Child(x))}}{size(Child(x))} \prod_{c \in Child(x)} cnt(c)\) Hal ini bisa didapatkan dari mengkombinasikan dengan stars and bars, atau multiple object combination terhadap urutan dari permutasi anak-anaknya.

Bagaimana cara menentukan ada berapa pasang $(i, j)$ yang kita ingin cari di awal tadi?

Untuk setiap root $R$, kita cari kemungkinan pasangan $i, j$ terjadi inversion dikalikan dengan $cnt(R)$. Perhatikan bahwa kita perlu mencari lca dari $i, j$ saat root saat ini $R$. Kita definisikan ini sebagai nilai dari $inv(i, j, R) = inv(i, j, lca(i, j, R))$. Sekarang kita akan mencari nilai dari $inv(i, j, p)$ untuk semua node $p$ yang berada di antara path $i$ dan $j$.

Untuk mencari nilai inv, pada intinya kita seperti mencari pada titik $p$, kemudian diberikan dua buah stack yang masing-masing mengarah ke-$i$ dan $j$, jadi intinya pengen tau yang sampai duluan yang mana. Kalau dipikirkan, nanti didapatkan bahwa dalam. katakanlah kedalaman stack pertama itu $a$ dan kedalaman kedua itu $b$. Nanti didapatkan kembali bahwa setelah $a + b - 1$ langkah pasti setidaknya salah satu dari mereka akan sampai, jadi sama saja sebenarnya dengan kita mencari binomial coefficient, dan menambahkan jumlahnya untuk yang angka lebih kecil, karena muncul belakangan. Bisa diprecompute menggunakan prefix-sum untuk perhitungan ini.

Total kompleksitas waktunya ialah $O(N^3 \log (N))$ yang merupakan waktu untuk mencari LCA juga. Kompleksitas $O(N^4)$ bakal TLE tho. Entah kenapa.