P4395 [BalticOI 2003] Gem Hovercraft

Given a tree, assign a weight to each node. The weight can be any positive integer. The only constraint is that two adjacent nodes cannot have the same weight. Find an assignment that minimizes the total weight of the entire tree.

The first line contains an integer $N$ representing the number of nodes in the tree, with $N \le 10000$. Each of the next $N-1$ lines indicates that two nodes $u,v(1\le u,v\le N)$ are connected by an edge.

The minimum possible total weight.

Translated by ChatGPT 5