This problem asks us to color the vertices of a tree with the minimum number of colors, such that no two nodes of the same color are adjacent or separated by only two edges. So if some node has $d$ neighbors, then all $d$ neighbors of the node, as well as the node itself, must receive pairwise distinct colors. Hence, if the maximum degree in the tree is $D$, then we need at least $D+1$ colors.

It turns out that $D+1$ colors are always sufficient; in fact, we'll show how to construct a valid $(D+1)$-coloring. Root the tree at an arbitrary vertex, and assign it color $1$. The root has at most $D$ children, so they can be assigned distinct colors in $\{2,\dots,D+1\}$. Now we have at most $D$ child subtrees, with the root of each subtree colored. Every node which has not been colored has distance $3$ or more from any node in a different subtree, so we can color the subtrees independently.

Pick a child $c$ of the root, and suppose that it has color $i \neq 1$. There are at most $D-1$ children of $c$, so they can be assigned distinct colors in $\{2,\dots,i-1, i+1, \dots, D+1\}$. Once again, the at most $D-1$ subtrees can now be colored independently.

This process continues until the tree is completely colored. In general, any non-root node $u$ has at most $D-1$ children, which can be assigned distinct colors in $\{1,\dots,D+1\}$ which avoid the color of $u$, and the color of $u$'s parent. This ensures that the coloring condition is satisfied: among any two adjacent nodes, one is a child of the other, and the child is assigned a different color from the parent. For any two nodes separated by at most two edges, there are two cases. If the nodes are siblings, then they are assigned distinct colors simultaneously. Otherwise, one node is the grand-child of the other, and so avoids the color of its grandparent.

Thus, the final algorithm is quite simple: compute the degree of every node, find the maximum, and add one. See my code below.

#include <iostream> using namespace std; int N,a,b; int d[100000]; int main() { cin >> N; for(int i=1;i<N;i++) { cin >> a >> b; d[a-1]++, d[b-1]++; } int D = 0; for(int i=0;i<N;i++) if(d[i] > D) D = d[i]; cout << D+1 << '\n'; }