P5765 [CQOI2005] Jewelry

There is a tree with $n$ nodes. Assign a positive integer label to each node so that adjacent nodes have different labels, and the total sum of labels is as small as possible.

The first line contains an integer $n$. The following $n-1$ lines each contain two integers $u, v \ (1\le u, v\le n)$, indicating that there is an edge between $u$ and $v$.

Only one line, the minimum possible sum of labels.

For $20\%$ of the testdata, $n\le 10$. For $40\%$ of the testdata, $n\le 1000$. For $100\%$ of the testdata, $1\le n\le 50000$. Translated by ChatGPT 5