I'm just wondering.. is there actually an official solution that runs in time for this problem? I find that pretty unlikely.. or if so, then it was extremely lucky to run in time.
The problem is quite famous (I studied it quite a bit when at university), and a brute force solution is, of course, hopeless. The only known way of solving it is to use approximation algorithms, genetic algorithms etc (starting with a randomly coloring, then trying to move towards a solution).
There have been many research papers written about this that I've found online, including one that solved all trees of size up to 28 or so - taking well over 10 seconds average to solve each one.
So no doubt if there is an official solution, the heuristics involved must only luckily work on the small sample of trees from the test data.. and I could come up with a tree on which it failed.
So, could we have some hints at what the test data alone is like, or what the lucky heuristics are, or change the bounds on the problem?
(I am, of course, talking about the small tree one, not the other trivial part).