You are given 2n alphabets a1, a2, ..., a{2n} with positive frequencies f1, f2, ..., f{2n} respectively. (We assume that f1 + f2 + ... + fn = 1.) Alphabets a1, a2, ..., an are colored blue, and alphabets a{n+1}, a{n+2}, ..., a{2n} are colored red. A prefix-free code C for {a1, a2, ..., a{2n}} is called valid if and only if every subtree of Trie(C) with at least two leaves has equal number of blue and red alphabets.

We need a polynomial time algorithm to find a valid prefix-free code of minimum cost. If possible explain running time analysis of algorithm.