1775【RMQamp;LCA】Closest Common Ancestors(最近公共祖先).doc

1775【RMQamp;LCA】Closest Common Ancestors(最近公共祖先) 导读：就爱阅读网友为您分享以下“1775【RMQamp;LCA】Closest Common Ancestors(最近公共祖先)”的资讯，希望对您有所帮助，感谢您对92的支持! 【RMQamp;LCA】Closest Common Ancestors（最近公 共祖先） Time Limit:1000MS Memory Limit:65536K Total Submit:3 Accepted:1 Description 最近公共祖先（cca.pas/c/cpp） 【问题描述】 输入一棵有根树和一系列顶点。对每对顶点(u，v)，算出它们的最近公共祖先。一个结点可以是它自己的祖先。(如例1中2的祖先是2和5) Input 每组数据输入格式： 第一行是一个整数n，表示顶点数，其中 n lt;= 900 ，接下来n行格式如下： vertex：(nr_of_successors) successor1 successor2 ... vertices是一个1到n的整数，表示顶点，nr_of_successors表示该顶点的儿子数，successor i( 1lt;=ilt;= nr_of_successors )表示该顶点的各儿子 然后是一个整数nr_of_pairs，表示要求的顶点对数 (u v) (x y) ... 输入包含至少一组数据 包含一些无用的空格，空行等 Output 对每个公共祖先程序输出这个祖先和以它为祖先的顶点对数。