最近公共祖先（LCA）
前言（需要图论和树的基础） LCA中文名最近公共祖先（LCA）类型题目。求LCA是一个基本的树上问题，说的就是这么一个事: 首先给出一棵树，然后随意制定两个结点，需要你找到这两个结点各自的所有公共的祖先结点中深度最深的一个结点。 下面我会从最基本的思路->不断优化的基本思路来扩展解决这类问题的解题思路。 最近公共祖先（LCA）原题 题目描述如题，给定一棵有根多叉树，请求出指定两
杂题——How many answers are wrong
How many answers are wrong FF是个熊男孩，他总是恳求TT和他一起玩接下来的游戏。 这是一个非常无聊的游戏：首先，TT写下一个整数序列。然后，FF从中选择一个连续的子序列（例如，从第3个整数到第5个整数的子序列），问TT他选择的 子序列的和是多少？接下来，TT将回答FF的问题。然后，重复这个过程，直到FF算出整个整数序列的和。 这真是一个非常非常无聊的游戏！TT根
杂题——最大gcd
最大gcd题目描述给定一个长度为n的数组a，你可以将其中的某个数字替换为任意一个其他数字（此操作只能执行一次，也可以不操作），请问最大可以使得整个数组的gcd为多少？ 输入格式第一行一个整数T表示测试用例个数。(1≤T≤1000) 对于每组测试用例： 第一行一个整数n(2≤n≤105)。 第二行n个整数表示数组a(1≤ai≤109)。 数据保证n≤106 输出格式对于每组测试用例，输出一个整数表示
杂题——小e跳房子
小e跳房子题目描述小e最近迷上了“跳房子”的游戏，房子在一条长度为n的横轴上，1是起点，n是终点。 小e从起点开始，每次可以往右跳一格（即使得当前的坐标位置+1），但是由于每个房子上面的摩擦系数μ不同，每次从房子i起跳时，有p i的概率因为脚滑回到起点（确实有点逆天），请问小e跳到终点的期望次数是多少？ 最后的结果对109+7取模。 输入格式第一行一个整数T表示测试用例个数。(1≤T≤1000)
杂题——吉利数组
L2-4：吉利矩阵所有元素为非负整数，且各行各列的元素和都等于 7 的 3×3 方阵称为“吉利矩阵”，因为这样的矩阵一共有 666 种。本题就请你统计一下，把 7 换成任何一个 [2,9] 区间内的正整数 L，把矩阵阶数换成任何一个 [2,4] 区间内的正整数 N，满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 N×N 方阵一共有多少种？ 输入格式：输入在一行中给出 2 个正整数
杂题——夺宝大赛
L3-1：夺宝大赛夺宝大赛的地图是一个由 n×m 个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻”是指两个方格有一条公共边）所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：
