Codeforces 778C. Peterson Polyglot(字典树合并)

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

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

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.

Examples
input

output

input

output

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.

题意:给出一颗字典树,现在问你删除那一层边后,剩余的节点数最少,删除之后下方的字典树可以发生合并,参见样例。

之前一直认为启发式合并是从小的向大的合并可以认为是logn的。看了官方题解上也是这么说的,就是暴力的启发式合并,每次找到最大的子树,然后其余的子树往里面合并就好了。但是因为每一层被删掉后的合并,都不能破坏原来的结构,因为你需要删除哪一层是一直在变化的。。。所以就可以借鉴一下可持久化的思想,新建节点来表示合并的一些节点。然而,看了看一些聚聚的代码发现,并没有采取这种启发式合并。

q聚交了个类似于线段树合并的做法。因为字典树和线段树都是结构确定的数据结构,所以他们的合并可以采取同一种方式。

然后思考一下这样的合并方式:发现操作的次数在于两棵树的公共节点,因为对于两棵树而言,他们之间的公共节点数肯定是小于等于小的那颗子树的节点数,也就可以被认为是一种天然的启发式合并了。所以复杂度也可以认为是O(nlogn)的。更多的细节可以看一看黄佳泰的线段树合并那个ppt。

然后回到这道题目,我们可以先dfs,弄出来每个节点的高度,以该节点为根的子树的大小,以及在某个高度以下的节点有多少个。。。

然后我们进行上面所说的合并过程,因为我们并不知道删去哪一层更好,所以可以再套一个dfs。每次合并的时候新开节点,然后我们统计一下合并某个节点的子树新的节点的节点数目,然后拿原来这一高度以下的节点数目减去。这样我们把所有的高度都搞完后,再扫一遍所有高度的cnt,就可以知道那一层最优了。

有个地方需要注意,就是再删除某一层的时候,如果这一层的叶子节点也是需要删除掉的。但是我看题意并没有看出来。。。。

终于搞过了这个卡了半天的题目。。。代码挺短的QAQ。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注