本文主要是介绍【LCA】vijos1427机密信息，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
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
【题解】用了比较暴力的染色法 s回溯到根，t回溯直到遇到第一个被染过色的点，即为最近公共祖先
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define maxn 10001char si[256];
int n,s,t,f[maxn],root,flag[maxn]={0},son[maxn],color[maxn],len[maxn];
int lenth,atime;int main()
{ scanf("%d%d%d\n",&n,&s,&t);int u,v,i;char c;for (i=1;i<=n;i++){scanf("%d%d%c%s\n",&u,&v,&c,&si);f[u]=v;flag[u]=1;son[v]++;len[u]=strlen(si);}for (i=1;i<=n;i++) if (!flag[i]){root=i; break;}int ts=s,tt=t;while (ts!=root){color[ts]=1;ts=f[ts];}while (!color[tt]){color[tt]=1;tt=f[tt];}root=tt;while (s!=root){lenth+=len[s];s=f[s];atime+=son[s];}while (t!=root){lenth+=len[t];t=f[t];atime+=son[t];} lenth+=len[root]; atime-=son[root];//祖先节点时间重复加了一次要减去printf("%d\n%d\n",lenth,atime);
}这篇关于【LCA】vijos1427机密信息的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
