MEXTREEMN - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: sheercold and Codula
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have a tree with N vertices. Assign a permutation P of [0, N-1] to the vertices of the tree so that \displaystyle\sum_{u=1}^N\sum_{v=u}^N f(u, v) is minimized, where f(u, v) is the mex of labels on the path between u and v.

EXPLANATION:

The labels of the vertices are distinct integers in [0, N-1], so each label will appear exactly once.
Let u_x denote the vertex with label x.

Now, u_0 is the only vertex with label 0.
So, any path that doesn’t contain u_0 will surely have a MEX of 0.
On the other hand, there are also definitely at least N paths that do contain u_0 (one path from u_0 to each vertex, including itself), and these N paths will hence have a MEX of (at least) 1.
So, no matter what we do, the answer is at least N.

Observe that it’s possible to ensure that there are exactly N paths that contain 0, by simply placing 0 at any leaf vertex.

The next question that should come to mind is: is it possible to make the answer exactly N?

Given that we already have N paths with positive MEX, this is only possible when these N paths all have a MEX of 1, and everything else has a MEX of 0.
It should be pretty obvious that it’s not possible to achieve this, for the simple reason that the path between u_0 and u_1 (i.e. the vertices whose labels are 0 and 1) will contain both 0 and 1, and so have a MEX of at least 2.

However, observe that if we place both 0 and 1 at leaf vertices (i.e. u_0 and u_1 are both leaves),

  • Paths not containing u_0 will have a MEX of 0.
  • There are N-1 paths from u_0 that don’t contain u_1.
    All of these will have a MEX of 1.
  • The path between u_0 and u_1 will have a MEX of at least 2.

For the last case, note that if we’re able to place the value 2 somewhere outside the (u_0, u_1) path, then the (u_0, u_1) path will have its MEX exactly equal to 2, which is optimal.
The actual answer in this case will be just (N-1) + 2 = N+1.

It’s almost always possible to achieve this: the only time it’s not possible is when the tree has exactly two leaves, i.e. looks like a path/bamboo.
Every tree that’s not just a path will have at least three leaves, so we can simply place 0, 1, 2 at any three leaves of the tree to achieve what we want: an answer of N+1.

For the path case, observe that no matter what we do, the MEX of the entire path is going to be N.
So, by placing 0 and 1 at the leaves of the path, we can ensure that the MEX equals (N-1)+N = 2N-1, which is optimal.

So finally: the answer is 2N-1 if the input graph is not a path graph, and N+1 otherwise.
Checking if a graph is a path graph is simple enough: you can check if every vertex has degree \leq 2 for example.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    degree = [0]*n
    for i in range(n-1):
        u, v = map(int, input().split())
        degree[u-1] += 1
        degree[v-1] += 1
    
    if max(degree) == 2: print(2*n-1)
    else: print(n+1)
1 Like