P7393 "TOCO Round 1" Eternal Star

"With sincere prayers." "At the moment when the stars fall." "Two figures are reflected in the water." "Shining together." 

Kuon wants a tree with as few nodes as possible. She will assign each node a positive integer label, such that adjacent nodes have different labels and the sum of all node labels is minimized. If there are multiple valid assignments, she will choose any one of them. Please help construct a tree such that, after Kuon finishes labeling it, the maximum label is guaranteed to be not less than $k$.

Two integers $k$ and $x$, where $k$ is as described in the statement, and $x$ is the scoring parameter.

The first line contains an integer $n$, the size of the tree you construct. The next $n - 1$ lines each contain two integers $u, v$, representing an edge of your tree.

The scoring is as follows. - If the constructed tree satisfies the requirements and $1 \le n \le x$, $1 \le u, v \le n$, then you will receive the full score for that test case. - Otherwise, you will receive $0$ points for that test case. | Test Point ID | $k$ | $x$ | | :-: | :-: | :-: | | $1$ | $1$ | $/$ | | $2$ | $2$ | $/$ | | $3$ | $3$ | $10$ | | $4$ | $3$ | $8$ | | $5$ | $4$ | $40$ | | $6$ | $4$ | $34$ | | $7$ | $5$ | $/$ | | $8\sim 16$ | $/$ | $/$ | | $17$ | $10$ | $53808$ | | $18\sim 19$ | $/$ | $/$ | | $20$ | $12$ | $519616$ | For $100\%$ of the testdata, $1 \le k \le 12$, $1 \le x \le 10^6$. For each test point, there is guaranteed to be a construction that can achieve full score. Translated by ChatGPT 5