Factor Tree

Chef lives in a country called ChefLand. The country can be represented as a tree of $N$ cities (numbered $1$ through $N$) connected by $N-1$ roads. For each valid $i$, the cost of a house in city $i$ is $A_i$. You should answer $Q$ queries. In each query, you are given cities $u$ and $v$ (possibly identical); Chef is planning to buy houses in these cities. Chef's *happiness quotient* is equal