/ JF_OIer / 题库 /

机密信息

机密信息

测试数据来自 system/1427

描述

Lorabit有个很奇怪的习惯,他把他所有的机密信息都存放在一个叫机密盘的磁盘分区里,然而这个机密盘中却没有一个文件,那他是怎么存放信息呢?聪明的你一定想到了,Lorabit的信息都是以文件夹名称的形式保存的。Lorabit给机密盘中的每一个文件夹都编了号,而Lorabit的机密信息是由S文件夹转到T文件夹的过程中必须经过的文件夹名称组合而成的(包括S和T),由于Lorabit的磁盘很慢,打开每个文件夹所耗费的时间等于该文件夹内下一级文件夹的数量。这次的任务是,给出每个文件夹的编号、名称以及它的父目录的编号和隐藏了Lorabit机密信息的起始文件夹编号和终点文件夹编号,你要计算出来的是Lorabit机密信息的长度以及寻找这个机密信息所需要的总时间。

格式

输入格式

输入文件的第一行为3个整数n、s、t,分别代表文件夹的个数、起始文件夹编号、终点文件夹编号,接下来n行,每行有2个整数i、pi和一个长度不超过255的字符串si(不包含空格),用空格分开,pi是i号文件夹的父目录编号(为0时表示该文件夹为根目录下的一级文件夹),si是i号文件夹的名称。

50%的数据是随机生成的;
60%的数据满足3<=n<=1000;
100%的数据满足3<=n<=10000、1<=i<=n、0<=pi<=n,保证一定有解。

输出格式

输出文件共2行,第一行是Lorabit的机密信息的长度,第二行是所消耗的时间。

样例1

样例输入1

6 1 5
1 2 Lo
2 3 ra
3 0 .
4 3 bi
5 4 t
6 5 .COM

样例输出1

8
4

限制

1 second

提示

假设你一开始就在初始文件夹位置,此时耗费的时间为0;你每打开一个文件夹,能够知道的文件夹名除了当前这个文件夹名之外,还有该文件夹内下一级的文件夹名。

来源

Conan From HNSDFZ

信息

ID
1020
难度
4
分类
树结构 | 最近公共祖先字符串 点击显示
标签
递交数
3
已通过
2
通过率
67%
上传者