We were waiting several weeks tp setting this contest and hope the problem was good enough.
I will write the full editorial in the few next days, now some hints and short solutions exist here.
Almost half of numbers are divisible by two.
For the string shouldn't be any i ≤ n - 2, si = si + 2. Make some examples of little sizes.
Find minimum weighted edges.
There is some edges with weight 0, try to connect them in a carefully way.
The last situation is some 'a' characters after some 'b' ones.
The last situation is unique.
The number of steps is also unique.
Each 'b' character makes a number of 'b' characters in the last situation according to the number of 'a' characters before it.
We want to color the ice creams in a way that all of ice creams in a vertex would be different and if two vertices &u& and &v& have ice cream i, then all of vertices in the unique path of u and v would have it.
Let's have a trivial upper-bound for the answer.
The trivial upper-bound should be maximum size of vertices' set.
You can prove that by induction on leaves of the tree. And code it how you proved it.
There were some opinion about this sentence of the problem:
Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.
A subgraph S of a graph G is a graph whose set of vertices and set of edges are all subsets of G. And according to this definition, the subgraph can also be empty as a subset of vertices and edges.
A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected. This definition means that the null graph and singleton graph are considered connected, while empty graphs on 2 ≤ n nodes are disconnected.
All of these definitions were from valid articles and it seems more logical. How ever, I should apologize all of the participants because of bad sample tests when some of articles and books didn't accept my opinion.
Let's solve the problem for just two tree. consider the trivial solution and try to improve it.
seems SQRT Decomposition.