Peterson Polyglot
Contest: Codeforces Round 402 (Div. 1)
Difficulty rating: 2500
Tags: brute force, dfs and similar, dsu, hashing, strings, trees

Peterson loves to learn new languages, but his favorite hobby is making new ones. Language is a set of words, and word is a sequence of lowercase Latin letters.

Peterson makes new language every morning. It is difficult task to store the whole language, so Peterson have invented new data structure for storing his languages which is called broom. Broom is rooted tree with edges marked with letters. Initially broom is represented by the only vertex — the root of the broom. When Peterson wants to add new word to the language he stands at the root and processes the letters of new word one by one. Consider that Peterson stands at the vertex u. If there is an edge from u marked with current letter, Peterson goes through this edge. Otherwise Peterson adds new edge from u to the new vertex v, marks it with the current letter and goes through the new edge. Size of broom is the number of vertices in it.

In the evening after working day Peterson can't understand the language he made this morning. It is too difficult for bored Peterson and he tries to make it simpler. Simplification of the language is the process of erasing some letters from some words of this language. Formally, Peterson takes some positive integer p and erases p-th letter from all the words of this language having length at least p. Letters in words are indexed starting by 1. Peterson considers that simplification should change at least one word, i.e. there has to be at least one word of length at least p. Peterson tries to make his language as simple as possible, so he wants to choose p such that the size of the broom for his simplified language is as small as possible.

Peterson is pretty annoyed with this task so he asks you for help. Write a program to find the smallest possible size of the broom and integer p.

Input format:
The first line of input contains integer n (2 ≤ n ≤ 3·105) — the size of the broom.

Next n - 1 lines describe the broom: i-th of them contains integers ui, vi and letter xi — describing the edge from ui to vi marked with letter xi.

Vertices are numbered from 1 to n. All xi are lowercase latin letters. Vertex 1 is the root of the broom.

Edges describe correct broom which is made from Peterson's language.

Output format:
The first line of output should contain the minimum possible size of the broom after its simplification. The second line of output should contain integer p to choose. If there are several suitable p values, print the smallest one.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Broom from the second sample test can be built using language "piece", "of", "pie", "pretty", "prefix". Its simplification with p = 2 obtains the language of words "pece", "o", "pe", "petty", "pefix". This language gives us the broom with minimum possible size.

Example input:
5
1 2 c
2 3 a
3 4 t
2 5 t

Example output:
3
2

Example input:
16
1 2 o
2 3 f
1 4 p
4 5 i
5 6 e
6 7 c
7 8 e
4 9 r
9 10 e
10 11 t
11 12 t
12 13 y
10 14 f
14 15 i
15 16 x

Example output:
12
2

Editorial:
While erasing letters on position p, trie changes like the following: all the edges from one fixed vertex of depth p are merging into one. You can see it on the picture in the sample explanation. After merging of the subtrees we have the only tree — union of subtrees as the result.
Consider the following algorithm. For every vertex v iterate over all the subtrees of v's children except for the children having largest subtree. There is an interesting fact: this algorithm works in $${\mathcal {O}}(n\log n)$$ in total.
Denote as sx the size of the subtree rooted at vertex x. Let hv be the v's child with the largest subtree, i.e. su ≤ shv for every u — children of v. If u is a child of v and u ≠ hv then $$s_u < \frac{s_v}{2}$$. Let's prove that.
1. Let $$s_{hv} < \frac{s_v}{2}$$. Then $$s_u \leq s_{h_v} < \frac{s_v}{2}$$ and $$s_u < \frac{s_v}{2}$$.
2. Otherwise, if $$s_{hv} \geq \frac{s_v}{2}$$, then we know that su + shv < sv. Therefore, $$s_u < s_v - s_{h_v} \Rightarrow s_u < s_v - \frac{s_v}{2} \Rightarrow s_u < \frac{s_v}{2}$$.
Consider vertex w and look at the moments of time when we have iterated over it. Let's go up through the ancestors of w. Every time we iterate over w the size of the current subtree becomes twice greater. Therefore we could't iterate over w more than $$\left\lceil \log _ { 2 } n \right\rceil$$ times in total. It proves that time complexity of this algorithm is $${\mathcal {O}}(n\log n)$$.
Solution:
1. Iterate over all integers p up to the depth of the trie
2. For every vertex v of depth p
3. Unite all the subtrees of v with running over all of them except for the largest one.
How to unite subtrees? First method. Find the largest subtree: it has been already built. Try to add another subtree in the following way. Let's run over smaller subtree's vertices and add new vertices into respective places of larger subtree. As the result we will have the union of the subtrees of v's children. All we need from this union is it's size. After that we need to roll it back. Let's remember all the memory cells, which were changed while merging trees, and their old values. After merging we can restore it's old values in reverse order.
Is it possible to implement merging without rolling back? Second method. Let's take all the subtrees except for the largest one and build their union using new memory. After that we should have two subtrees: the largest one and the union of the rest. We can find size of their union without any changes. Everything we need is to run over one of these trees examining another tree for the existence of respective vertices. After this we can reuse the memory we have used for building new tree.