You are given a rooted tree with $$$n <= 1e5$$$ nodes. Each node has a number $$$a[i] <= n$$$ written on it. A path has a dominant element when the most frequently occuring element appears more than $$$path length/2$$$ times. Count how many paths with a dominant element there are.

You are given n <= 1e6 numbers, all a[i] <= 1e6, among all pairs of indices (i, j), such that i != j you need to find the maximum value of (a[i] + a[j]) * (j — i). Only one solution involving something similar to D&C DP optimization is known to me, are there any others?