什么是LCA LCA（Lowest Common Ancestors）最近公共祖先  对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u和v的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。  来看张图   在这里，可以说5 6的最近公共祖先为2，同样的，3 8 的最近公共祖先为2所以，在这里应该可以理解这个概念了 模板题：NKOJ最近公共祖先 题目  给出一棵有N(编号1到N)个节点的有根树，求出指定节点对的最近公共祖先！ 对于树中节点x而言，从根节点到达x的这一条路径中经过的所有节点，都称为x的祖先。如上图所表示的树中， 根节点为8。8、...

让我们先看一道题 题目 或许你不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，就可以判断两个人是否亲戚，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那检验亲戚关系实非人力所能及。 在这种情况下，最好的帮手就是计算机。你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和Ben是戚，等等。从这些信息中，你可以推出Marry和Ben 是亲戚。 请写一个程序，对于亲戚关系的提问，快速给出答案。 输入 输入由两部分组成：  第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的编号为1...

A.616问题(签到) 题目 子串是连续的。 果老师最喜爱的字符串是616。 果老师得到了一个纯数字的字符串S，他想知道在可以任意打乱顺序的情况下，最多有多少个不同的子串为616。 当两个子串 S1[l1...r1],S2[l2....r2] 满足 l1不等于l2且r1不等于r2或时它们被认为是不同的。 Input  1111451419266  Output  1  思路  只需要考虑1和6的个数 让616最多的格式为6161616.....让前后字符串共用6，6的个数比1的个数多一。 设1的个数为cnt1,6的个数为cnt6，则616个数为cnt6-1或者cnt1的个数，取最小值即可，注意...