标签 - LCA

? 解题记录 ? ? BZOJ ? ? LCA ? ? 倍增 ? ? 补档计划第一期 ?    2017-10-01 14:20:57    427    0    0
Input Output Sample Input 6 4  1 2  2 3  2 4  4 5  5 6  4 5 6  6 3 1  2 4 4  6 6 6Sample Output 5 2  2 5  4 1  6 0Hint 不算难的LCA,对于三个人两两求出LCA并根据深度计算即
? 解题记录 ? ? 洛谷 ? ? LCA ? ? 树链剖分 ? ? 模板 ?    2017-07-29 14:03:13    284    0    0
题目描述如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入输出格式输入格式:   第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。 接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。 接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。   输出格式:   输出包含M行,每行包含一个正整数,依次为每一个询问的结果。   输入输出样例输入样例#1:5 5 4 3 1 2 4 5 1
? 解题记录 ? ? 洛谷 ? ? LCA ? ? 倍增 ? ? 模板 ?    2017-07-18 11:19:55    282    0    0
题目描述如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入输出格式输入格式:   第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。 接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。 接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。   输出格式:   输出包含M行,每行包含一个正整数,依次为每一个询问的结果。   输入输出样例输入样例#1:5 5 4 3 1 2 4 5 1