F. Peterson Polyglot

Codeforces

IDCF779F

Time4000ms

Memory512MB

Difficulty—

strings

English · Original

Chinese · Translation

Formal · Original

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 _u__i_, _v__i_ and letter _x__i_ — describing the edge from _u__i_ to _v__i_ marked with letter _x__i_. Vertices are numbered from 1 to _n_. All _x__i_ 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. [samples] ## Note ![image](https://espresso.codeforces.com/34e91571f3b5d54da921c76053c7a4709d59d1bc.png) 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.

Peterson 喜欢学习新语言，但他最钟爱的爱好是创造新语言。语言是一组单词的集合，而单词是由小写拉丁字母组成的序列。 Peterson 每天早上都会创造一种新语言。由于存储整个语言很困难，Peterson 发明了一种名为 #cf_span(class=[tex-font-style-underline], body=[broom]) 的新数据结构来存储他的语言。Broom 是一棵边被字母标记的有根树。最初，broom 仅由一个顶点——根组成。当 Peterson 想要向语言中添加一个新单词时，他从根开始，逐个处理新单词的字母。假设 Peterson 当前位于顶点 #cf_span[u]。如果从 #cf_span[u] 出发有一条标有当前字母的边，Peterson 就沿着这条边移动；否则，他创建一条从 #cf_span[u] 到新顶点 #cf_span[v] 的边，用当前字母标记这条边，然后移动到新顶点。Broom 的大小是其中顶点的数量。在傍晚工作结束后，Peterson 无法理解他早上创造的语言——这对他来说太难了，于是他试图简化它。语言的简化过程是：从某些单词中删除一些字母。形式上，Peterson 选择一个正整数 #cf_span[p]，并从所有长度至少为 #cf_span[p] 的单词中删除第 #cf_span[p] 个字母（单词中的字母编号从 1 开始）。Peterson 认为简化必须至少改变一个单词，即必须存在至少一个长度至少为 #cf_span[p] 的单词。Peterson 希望让他的语言尽可能简单，因此他希望选择一个 #cf_span[p]，使得简化后语言的 broom 大小最小。 Peterson 对这个任务感到非常烦恼，因此他向你求助。请编写一个程序，找出可能的最小 broom 大小以及对应的整数 #cf_span[p]。输入的第一行包含整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 3·10^5]）——broom 的大小。接下来的 #cf_span[n - 1] 行描述 broom：第 #cf_span[i] 行包含整数 #cf_span[ui]、#cf_span[vi] 和字母 #cf_span[xi]，表示从 #cf_span[ui] 到 #cf_span[vi] 且标记为 #cf_span[xi] 的边。顶点编号从 1 到 #cf_span[n]。所有 #cf_span[xi] 均为小写拉丁字母。顶点 1 是 broom 的根。这些边描述的是由 Peterson 的语言构建的正确 broom。输出的第一行应包含简化后 broom 的最小可能大小。第二行应包含要选择的整数 #cf_span[p]。如果有多个合适的 #cf_span[p] 值，请输出最小的那个。第二个样例测试中的 broom 可以通过语言 "piece"、"of"、"pie"、"pretty"、"prefix" 构建。其在 #cf_span[p = 2] 下的简化版本得到语言 "pece"、"o"、"pe"、"petty"、"pefix"。这个语言给出了最小可能大小的 broom。 ## Input 输入的第一行包含整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 3·10^5]）——broom 的大小。接下来的 #cf_span[n - 1] 行描述 broom：第 #cf_span[i] 行包含整数 #cf_span[ui]、#cf_span[vi] 和字母 #cf_span[xi]，表示从 #cf_span[ui] 到 #cf_span[vi] 且标记为 #cf_span[xi] 的边。顶点编号从 1 到 #cf_span[n]。所有 #cf_span[xi] 均为小写拉丁字母。顶点 1 是 broom 的根。这些边描述的是由 Peterson 的语言构建的正确 broom。 ## Output 输出的第一行应包含简化后 broom 的最小可能大小。第二行应包含要选择的整数 #cf_span[p]。如果有多个合适的 #cf_span[p] 值，请输出最小的那个。 [samples] ## Note 第二个样例测试中的 broom 可以通过语言 "piece"、"of"、"pie"、"pretty"、"prefix" 构建。其在 #cf_span[p = 2] 下的简化版本得到语言 "pece"、"o"、"pe"、"petty"、"pefix"。这个语言给出了最小可能大小的 broom。

**Definitions** Let $ T $ be a rooted tree with $ n $ vertices (labeled $ 1 $ to $ n $), where vertex $ 1 $ is the root. Each edge from parent $ u $ to child $ v $ is labeled with a lowercase Latin letter $ x $. The tree $ T $ represents a language $ L $: each leaf corresponds to a word (the concatenation of edge labels along the path from root to leaf). Let $ \ell(w) $ denote the length of word $ w \in L $. **Constraints** 1. $ 2 \le n \le 3 \cdot 10^5 $ 2. The tree is valid: exactly $ n-1 $ edges, connected, rooted at 1. 3. All edge labels are lowercase Latin letters. 4. Each word in $ L $ is the string formed by the edge labels on the unique root-to-leaf path. **Objective** Find the smallest integer $ p \ge 1 $ such that: - For every word $ w \in L $ with $ \ell(w) \ge p $, we remove the $ p $-th letter (1-indexed) to form a new word $ w' $. - The resulting set $ L' = \{ w' \mid w \in L, \ell(w) \ge p \} \cup \{ w \mid w \in L, \ell(w) < p \} $ has minimal possible size (i.e., minimal number of distinct words). - Among all such $ p $ minimizing $ |L'| $, choose the smallest $ p $. Output: - The minimal size of the broom (i.e., number of distinct words in $ L' $) - The smallest such $ p $ **Note**: The broom for $ L' $ is the trie (prefix tree) built from $ L' $.

Samples

Input #1

Output #1

3
2

Input #2

Output #2

12
2

API Response (JSON)

{
  "problem": {
    "name": "F. Peterson Polyglot",
    "description": {
      "content": "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 morn",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF779F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\nPeterson makes new language every morn...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Peterson 喜欢学习新语言，但他最钟爱的爱好是创造新语言。语言是一组单词的集合，而单词是由小写拉丁字母组成的序列。\n\nPeterson 每天早上都会创造一种新语言。由于存储整个语言很困难，Peterson 发明了一种名为 #cf_span(class=[tex-font-style-underline], body=[broom]) 的新数据结构来存储他的语言。Broom 是一棵边被字母标记...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T $ be a rooted tree with $ n $ vertices (labeled $ 1 $ to $ n $), where vertex $ 1 $ is the root.  \nEach edge from parent $ u $ to child $ v $ is labeled with a lowercase Lati...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments