Hello everyone!

In this blog, I will describe an (O(n)) construction for E. Building a Tree.

The main ideas are:

• checking the valid range of (k);
• rooting the tree at vertex (1);
• separating even and odd vertices into two branches;
• reducing the required distance sum to a depth sum;
• greedily assigning depths.

  1. Problem Restatement

We need to construct a tree with vertices (1,2,\ldots,n) such that

Equivalently,

If no such tree exists, we output (-1).

2. Necessary Conditions

For any edge of the tree, removing it splits the tree into two connected components.

While traversing the cyclic order

every time we cross from one component to the other, we must later cross back.

Therefore, every edge contributes an even number of times to the total sum, so

must be even.

Also, every edge of the tree is used at least twice. Since a tree has (n-1) edges,

The maximum possible value is

Thus, a solution exists only if

and

In the code:

ll mn = 2LL * (n - 1);
ll mx = 1LL * n * n / 2;

if (k % 2 || k < mn || k > mx) {
    cout << -1 << '\n';
    return;
}

3. Two-Branch Construction

Root the tree at vertex (1).

All even vertices belong to one branch, and all odd vertices greater than (1) belong to another branch.

For example:

        1
      /   \
     2     3
     |     |
     4     5
     |     |
     6     7

The branches do not need to be simple paths. A vertex may be connected to any earlier vertex of the same parity.

The important property is that every consecutive pair (i,i+1) has opposite parity.

Hence, for every

the path from (i) to (i+1) passes through vertex (1), so

The pairs ((1,2)) and ((n,1)) contribute

and

respectively.

Therefore, every non-root vertex contributes its depth exactly twice:

So we only need

In the code:

ll rem = k / 2;

Here, rem is the remaining depth sum that still needs to be assigned.

4. Stored Information

For each parity, we maintain:

vector<vector<int>> rep(2, vector<int>(n + 1));
int dep[2] = {0, 0};

The meaning is:

• dep[p] is the maximum depth currently used by parity p;
• rep[p][d] stores one vertex of parity p at depth d.

For a vertex (v),

int p = v & 1;

determines its parity.

If we want to place (v) at depth (d>1), we need an existing vertex of the same parity at depth (d-1).

Therefore,

This is represented by

int lim2 = dep[p] + 1;

5. Greedy Choice

Suppose we are processing vertex (v).

After processing it, there are

int lef = n - v;

vertices remaining.

Every remaining vertex must have depth at least (1). Therefore, we must reserve at least lef units of the remaining sum.

Thus, the current depth cannot exceed

ll lim1 = rem - lef;

The tree structure gives another upper bound:

int lim2 = dep[p] + 1;

Therefore, we choose

int d = min<ll>(lim1, lim2);

This assigns the largest possible valid depth to the current vertex while leaving enough depth for the remaining vertices.

If

d < 1

then the construction is impossible:

if (d < 1) {
    cout << -1 << '\n';
    return;
}

6. Choosing the Parent

If the chosen depth is (1), the vertex is connected directly to the root:

if (d == 1)
    u = 1;

Otherwise, we connect it to a vertex of the same parity at depth (d-1):

else {
    u = rep[p][d - 1];
    if (!u) {
        cout << -1 << '\n';
        return;
    }
}

Then we store the edge:

ans.push_back({u, v});

and update the data structures:

rep[p][d] = v;
dep[p] = max(dep[p], d);

Finally, subtract the assigned depth from the remaining sum:

rem -= d;

7. Why the Greedy Works

The greedy uses two limits.

First,

d <= dep[p] + 1

guarantees that the chosen depth is constructible.

If (d=1), we connect to vertex (1).

If (d>1), a vertex at depth (d-1) already exists in the same parity branch and is stored in

rep[p][d - 1].

Second,

d <= rem - lef

guarantees that at least one unit remains for every unprocessed vertex.

So the algorithm never spends too much of the remaining depth sum.

After processing all vertices, the construction is valid only if

rem == 0

which is checked by

if (rem) {
    cout << -1 << '\n';
    return;
}

Then

and therefore

8. Complexity

Each vertex is processed exactly once.

The time complexity is

The memory complexity is

9. Implementation

https://codeforces.me/contest/2247/submission/384493178

Thanks for reading!