CF601D Acyclic Organic Compounds

You are given a tree $ T $ with $ n $ vertices (numbered $ 1 $ through $ n $ ) and a letter in each vertex. The tree is rooted at vertex $ 1 $ . Let's look at the subtree $ T_{v} $ of some vertex $ v $ . It is possible to read a string along each simple path starting at $ v $ and ending at some vertex in $ T_{v} $ (possibly $ v $ itself). Let's denote the number of distinct strings which can be read this way as . Also, there's a number $ c_{v} $ assigned to each vertex $ v $ . We are interested in vertices with the maximum value of . You should compute two statistics: the maximum value of  and the number of vertices $ v $ with the maximum .

N/A

N/A

In the first sample, the tree looks like this: The sets of strings that can be read from individual vertices are: Finally, the values of  are: In the second sample, the values of  are $ (5,4,2,1,1,1) $ . The distinct strings read in $ T_{2} $ are ; note that  can be read down to vertices $ 3 $ or $ 4 $ .