Problem: 2155F - Juan's Colorful Tree

For this problem, it turns out that if you just iterate over the colors in the smaller of the two sets $$$C_u$$$ and $$$C_v$$$ (and also de-dupe queries), total complexity is bounded by something like $$$s \sqrt {q}$$$. More generally, let's say we have an array $$$a_i$$$ such that $$$\sum a_i = s$$$. If we pick $$$q$$$ distinct pairs of indices $$$x_i \leq y_i$$$, then it turns out that over all possible choices, $$$\sum \min(a_{x_i}, a_{y_i})$$$ is bounded by $$$s \sqrt {q}$$$. Equality is achieved when $$$a$$$ has $$$\sqrt{q}$$$ values equal to $$$\frac{s}{\sqrt{q}}$$$, and all other values equal to $$$0$$$.

Are there any other problems that use this very interesting bound?