CF778C Peterson Polyglot

彼得森热爱学习新语言，但他最喜欢的爱好是创造新语言。一个语言是一些单词的集合，一个单词是由小写拉丁字母组成的序列。 彼得森每天早晨都会创造一种新语言。存储整个语言是一项困难的任务，因此彼得森发明了一种新的数据结构来存储他的语言，这种结构称为“扫帚”。扫帚是一个有根树，边上标有字母。最初，扫帚只有一个顶点——扫帚的根。当彼得森想把一个新单词加入到语言里时，他站在根节点上，一次处理该单词的每个字母。假设彼得森当前在顶点 $u$。如果从 $u$ 有一条用当前字母标记的边，那么彼得森就沿着这条边前进。否则，他就在 $u$ 新建一条边通往新顶点 $v$，用当前字母标记，并沿着这条新边前进。扫帚的大小指的是其中顶点的数量。 一天工作结束后，彼得森发现自己已经无法理解早上造出的语言了。对于感到无聊的彼得森来说，这太复杂了，因此他尝试简化语言。简化语言的过程是从一些单词中删去一些字母。形式化地说，彼得森选择一个正整数 $p$，并将所有长度至少为 $p$ 的单词的第 $p$ 个字母删除。单词中的字母从 1 开始编号。彼得森认为，简化操作必须改变至少一个单词，即必须存在长度至少为 $p$ 的单词。彼得森希望让自己的语言尽可能简单，所以他想选择 $p$，使得简化后的扫帚大小最小。 彼得森对此任务感到不胜其烦，于是请你帮忙。请写一个程序，计算简化后的扫帚最小可能大小和应该选择的 $p$。如果有多个合适的 $p$，输出最小的那个。

第一行输入一个整数 $n$（$2 \leq n \leq 3 \cdot 10^{5}$），表示扫帚的大小。 接下来的 $n-1$ 行描述扫帚的结构：第 $i$ 行包含整数 $u_{i}$、$v_{i}$ 和字母 $x_{i}$，表示从 $u_{i}$ 到 $v_{i}$ 有一条由字母 $x_{i}$ 标记的边。 顶点编号从 1 到 $n$。所有 $x_{i}$ 都是小写拉丁字母。顶点 1 是扫帚的根节点。 这些边描述了根据彼得森的语言构建的合法扫帚。

输出两行。第一行输出简化后扫帚的最小可能大小。第二行输出应选择的 $p$。如果有多个合适的 $p$，输出最小的那个。

 第二个样例中的扫帚可以通过语言 "piece"、"of"、"pie"、"pretty"、"prefix" 构建。它在 $p=2$ 时进行简化得到了单词 "pece"、"o"、"pe"、"petty"、"pefix"。这个语言对应的扫帚大小最小。 由 ChatGPT 5 翻译