Codeforces Round #721 MEX Tree Solution (Java/C++)

Solution:

Use the node 0 as the root of tree. For each node, calculate the total number of children nodes (include itself) by DFS. Denote by "count".

For k=0. It's obviously. Just not pass through the root of tree. So the result is: $\sum_{child}{C_{child.count}^2}$.

If k=1. So it must pass through the root of tree, and not pass-through node 1. So just pick one node from any side. And pair it with any other nodes.

For other cases, and for any k. The shortest path of u and v must cover all nodes from 0 to k-1. So, once there is a branch between 0 and k-1, then all the subsequent k's result is 0.

So, after node 0 and node 1, We can get a list (at beginning, the list only has node 0 and node 1). Let us keep track the two ends of this list. For each k, we can choose one point from both ends.

Code:

Java

Submission #117023767 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #117027176 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge