{"problem":{"name":"Ex - Optimal Path Decomposition","description":{"content":"You are given a tree with $N$ vertices numbered $1$ through $N$. The $i$\\-th edge connects vertex $A_i$ and vertex $B_i$. Find the minimum integer $K$ such that you can paint each vertex in a color so","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc293_h"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices numbered $1$ through $N$. The $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.\nFind the minimum integer $K$ such that you can paint each vertex in a color so that the following two conditions are satisfied. You may use any number of colors.\n\n*   For each color, the set of vertices painted in the color is connected and forms a simple path.\n*   For all simple paths on the tree, there are at most $K$ distinct colors of the vertices in the path.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The given graph is a tree.\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc293_h","tags":[],"sample_group":[["7\n3 4\n1 5\n4 5\n1 2\n7 4\n1 6","3\n\nIf $K=3$, the conditions can be satisfied by painting vertices $1,2,3,4$, and $5$ in color $1$, vertex $6$ in color $2$, and vertex $7$ in color $3$. If $K \\leq 2$, there is no way to paint the vertices to satisfy the conditions, so the answer is $3$."],["6\n3 5\n6 4\n6 3\n4 2\n1 5","1"],["9\n1 3\n9 5\n8 7\n2 1\n5 2\n5 8\n4 8\n6 1","3"]],"created_at":"2026-03-03 11:01:14"}}