Description
有个很奇怪的习惯，他把他所有的机密信息都存放在一个叫机密盘的磁盘分区里，然而这个机密盘中却没有一个文件，那他是怎么存放信息呢？聪明的你一定想到了，
的信息都是以文件夹名称的形式保存的。
给机密盘中的每一个文件夹都编了号，而
的机密信息是由
文件夹转到
文件夹的过程中必须经过的文件夹名称组合而成的(包括
和
)，由于
的磁盘很慢，打开每个文件夹所耗费的时间等于该文件夹内下一级文件夹的数量。这次的任务是，给出每个文件夹的编号、名称以及它的父目录的编号和隐藏了
机密信息的起始文件夹编号和终点文件夹编号，你要计算出来的是
机密信息的长度以及寻找这个机密信息所需要的总时间。
Input
输入文件的第一行为个整数
，分别代表文件夹的个数、起始文件夹编号、终点文件夹编号.
接下来行，每行有
个整数
和
个字符串
(不包含空格),用空格分开，
是
号文件夹的父目录编号(为
时表示该文件夹为根目录下的一级文件夹)，
是
号文件夹的名称.
Output
输出文件共行，第一行是
的机密信息的长度，第二行是所消耗的时间.
Sample Input
6 1 5
1 2 Lo
2 3 ra
3 0 .
4 3 bi
5 4 t
6 5 .COM
Sample Output
8
4
HINT
,保证一定有解.
假设你一开始就在初始文件夹位置，此时耗费的时间为0；你每打开一个文件夹，能够知道的文件夹名除了当前这个文件夹名之外，还有该文件夹内下一级的文件夹名.
Solution
这道题就是裸的...
记录打开根节点到
的路径上的文件夹所需时间和.
记录根节点到
的路径上的文件夹名称长度和.
只是有以下细节需要注意:
对于,不需要算
的打开时间;有可能
在一条链上.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define K 15
#define M 305
#define N 10005
using namespace std;
struct graph{
int nxt,to;
}e[N];
int f[N][K],g[N],len[N],tim[N],fa[N],dep[N],n,s,t,cnt;
char c[M];stack<int> sta;
inline void addedge(int x,int y){
e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline void dfs(int r){
int u;dep[r]=;sta.push(r);
for(int i=;i<K;++i)
f[r][i]=r;
while(!sta.empty()){
u=sta.top();sta.pop();
if(u!=r) for(int i=;i<K;++i)
f[u][i]=f[f[u][i-]][i-];
for(int i=g[u];i;i=e[i].nxt){
f[e[i].to][]=u;
sta.push(e[i].to);
tim[e[i].to]+=tim[u];
len[e[i].to]+=len[u];
dep[e[i].to]=dep[u]+;
}
}
}
inline int swim(int x,int h){
for(int i=;h;i++,h>>=)
if(h&) x=f[x][i];
return x;
}
inline int lca(int x,int y){
if(dep[x]<dep[y]){
int tem=x;x=y;y=tem;
}
x=swim(x,dep[x]-dep[y]);
if(x==y) return x;
int i;
while(true){
for(i=;f[x][i]!=f[y][i];++i);
if(!i) return f[x][];
x=f[x][i-];y=f[y][i-];
}
}
inline void init(){
scanf("%d%d%d",&n,&s,&t);
for(int i=,j,k;i<=n;++i){
scanf("%d%d%s",&j,&k,c);
addedge(k,j);
len[j]=strlen(c);
++tim[k];fa[j]=k;
}
tim[]=;dfs();
int k=lca(s,t);
if(s==t) printf("%d\n%d\n",len[s],);
else if(k==s) printf("%d\n%d\n",len[s]+len[t]-len[k]-len[fa[k]],tim[fa[t]]-tim[s]);
else if(k==t) printf("%d\n%d\n",len[s]+len[t]-len[k]-len[fa[k]],tim[fa[s]]-tim[fa[t]]);
else printf("%d\n%d\n",len[s]+len[t]-len[k],tim[fa[s]]+tim[fa[t]]-tim[k]);
}
int main(){
freopen("folder.in","r",stdin);
freopen("folder.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}