Brute force in $$$\mathcal{O}(nm^2)$$$ can pass problem D.

Submission

Segment tree for C2 seems like a bit of overkill. You can keep vector of sets of indices in b for each element of a. (including m+i, or just any large const, if you allow non-strict increasing arrays instead). Then, for each update you just need to check whether the increase condition still holds for the adjacent pairs and update the counter. If the counter is full, yield YA.

FINALLY.

My solution to E3:

Call a node "special" if it is one of the $$$p$$$ given nodes. Call a node "chosen" if it is one of the $$$k$$$ nodes in the chosen subset.

Build the Kruskal Reconstruction Tree (KRT) of the graph, with $$$2n - 1$$$ nodes. All nodes in the original graph are given the same label in the KRT.

For some special node $$$x$$$, let $$$y$$$ be the lowest ancestor of $$$x$$$ in the KRT with at least one chosen node in the subtree of $$$y$$$. The maximum edge weight needed to get to a chosen node from special node $$$x$$$ in the original graph, is the weight of the edge that corresponds to $$$y$$$ in the KRT.

I then transformed this problem a bit. Let $$$f(i)$$$ be the edge weight that corresponds to node $$$i$$$ in the KRT (if $$$i \leq n$$$, then $$$f(i) = 0$$$). Let $$$g(i)$$$ be the number of special leaves in the subtree of $$$i$$$ in the KRT. Let the the value of a node $$$i$$$ be $$$g(i) * (f(i) - f(par[i]))$$$. Choose $$$k$$$ leaves in the KRT, to minimize the sum of values of nodes which have at least one chosen leaf in its subtree.

This works, because the contribution of some special node $$$x$$$ will be $$$(f(y) - f(par[y])) + (f(par[y]) - f(par[par[y]])) + \dots = f(y)$$$, where $$$y$$$ is the lowest ancestor of $$$x$$$ with a special node in its subtree.

After this round my rating increased to 1399, and i am very grateful to the rating system.

E is very nice. Learn a new trick about how to use minimum spanning tree in this.
Btw, editorial E only E3 ?!

I was gonna say D is chaotic until I saw this implementation (ecnerwala's). Insane

athin Kinon "It turns out that the strategy above is also the optimal strategy for the original version of the problem. So we can simulate that process to get the answer" proof please?

Explain to me, plz, algorithm for E1. Most of the solutions use Floyd-Warshall algorithm to calculate distances between vertices. Then for each k they greedily find next vertex to install server, and this vertex should reduce current latency the most. So if we have set of vertices-servers on the step k, then solution for k+1 contains all these vertices plus another one that have met the criteria I've described above. While it's clear for me that we should install servers in vertices where we need servers (and do not consider other vertices as candidates), it's more complicated to prove optimality of greediness on each step for k. Can you explain me, why greedy solution would be globally optimal?

For example, for k=1 I have to put server in vertex, say, 3. Why it's not possible for k=2 to have set of vertices (1, 2) as optimal solution so that latency of (1, 2) solution is less than (3, 1) or (3, 2) or any other (3, *) solutions?

Please make Editorial for each part of the problem E.

Both solutions for C2 had a level of math observation way beyond me, I solved C1 almost exactly mentioned in the editorial yet failed to even come close to the required idea for C2. Anyway segtree seemed the more approachable of the two so here's a segtree submission which is relatively clean for reference: https://mirror.codeforces.com/contest/2021/submission/285002624

Super slow editorial :(

I waited for days to see the official editorial for E3 and what I see now is coming soon. The time is enough to see the accepted code by myself and understand the idea of KRT.

Editorial for E1&E2:

Firstly, it is not hard to find out that the graph can be reduced to its minimum spanning tree since only the max value on the path is concerned.

Now, suppose the tree $$$T$$$ is in the form of $$$A-e-B$$$, where A and B are two subtrees and $$$e$$$ is the edge of the large value in the graph. Define $$$DP_A[i]$$$ where $$$(1\le i \le n))$$$ as the sum of latencies in A if we place $$$i$$$ servers there, similarly for $$$DP_B$$$ and $$$DP_{T}$$$.

To calculate $$$DP_{T}[i]$$$(which means the total latency given $$$i$$$ servers can be installed in $$$T = A-e-B$$$), notice that there are exactly three scearios:

1. All $$$i$$$ servers are in $$$A$$$, $$$DP_A[i] + len_e * size(B)$$$
2. All $$$i$$$ servers are in $$$B$$$, $$$DP_B[i] + len_e * size(A)$$$
3. $$$j$$$ servers are in $$$A$$$ and $$$i-j$$$ servers are in $$$B$$$, $$$DP_A[j] + DP_B[i-j]$$$

where $$$size()$$$ means the number of houses requiring the internet.

Now we can do the calculation recursively.(Actually you will do it bottom up)

Editorial for E3:

TLDR: The DP array actually forms a convex hull, which is intuitive since the marginal benefit when you installing a new server is decreasing. Hence when calculating the transitions, the so-called Minkowski addition can be applied to accelerate.