寒假集训2.28-171主机测评

第一题：互相攻击

题目描述

有一张无限大的棋盘（可以认为是一个无限大的方格平面）。

现在棋盘上放了 k 个棋子，第 i 个棋子位于坐标 (ri,ci)（行、列坐标均为整数）。

如果两枚棋子满足

∣r1−r2∣=∣c1−c2∣

则认为它们可以相互攻击。

请你计算：一共有多少对棋子可以相互攻击。

输入格式

第一行一个整数 k，表示棋子个数。

接下来 k 行，每行两个整数 ri,ci，表示第 i 个棋子所在的行与列。

输出格式

输出一个整数，表示可以相互攻击的棋子对数。

输入输出样例

输入 #1

2
1 1
3 3

输出 #1

输入 #2

3
1 2
2 3
4 1

输出 #2

输入 #3

4
2 1
3 2
4 3
5 4

输出 #3

输入 #4

6
1 1000000000
2 999999999
3 999999998
999999998 3
999999999 2
1000000000 1

输出 #4

说明/提示

对于样例 1：两枚棋子分别在 (1,1) 与 (3,3)，满足 ∣1−3∣=∣1−3∣，因此它们可以互相攻击，答案为 1。

对于样例 2：(1,2) 与 (2,3) 在同一条对角线上，(2,3) 与 (4,1) 在同一条对角线上，因此答案为 2。

对于样例 3：这四枚棋子在同一条对角线上，共有 6 对可以互相攻击。

数据范围：本题数据分布严格如下表所示：

数据占比约束条件

30%	1≤k≤103，1≤ri,ci≤103
30%	1≤k≤105，1≤ri,ci≤103
40%	1≤k≤105，1≤ri,ci≤109

思路：

边走边计算。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long k,r[100100],c[101000],d,f;
unsigned long long ans;
map<long long,long long> cnt1,cnt2;
int main(){
cin>>k;
for(int i=1;i<=k;i++){
cin>>r[i]>>c[i];
ans+=cnt1[r[i]-c[i]]+cnt2[r[i]+c[i]];
cnt1[r[i]-c[i]]++;
cnt2[r[i]+c[i]]++;
}
cout<<ans;
return 0;
}

提高：

C++ map 的基本概念

C++ 中的 map 是一种关联容器，存储键值对（key-value pairs），其中每个键唯一且按特定顺序排列。基于红黑树实现，map 提供了高效的查找、插入和删除操作，时间复杂度为 O(log n)。

声明和初始化

使用 map 需要包含头文件 <map>，并通过模板参数指定键和值的类型：

#include <map>
std::map<int, std::string> myMap;

初始化方式包括直接赋值或列表初始化（C++11 及以上）：

std::map<int, std::string> myMap = {{1, "apple"}, {2, "banana"}};

插入元素

插入元素可以使用 insert 方法或 operator[]：

myMap.insert(std::make_pair(3, "cherry"));
myMap[4] = "date";

注意：operator[] 在键不存在时会自动创建新条目，而 insert 不会覆盖已存在的键。

访问元素

通过键访问值可以使用 operator[] 或 at 方法：

std::string fruit = myMap[1]; // 返回 "apple"
std::string fruit2 = myMap.at(2); // 返回 "banana"

at 方法在键不存在时会抛出 std::out_of_range 异常，而 operator[] 会插入默认值。

遍历元素

使用迭代器或范围循环（C++11 及以上）遍历 map：

for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

查找元素

使用 find 方法检查键是否存在：

auto it = myMap.find(3);
if (it != myMap.end()) {
std::cout << "Found: " << it->second << std::endl;
}

删除元素

通过键或迭代器删除元素：

myMap.erase(3); // 删除键为 3 的元素
auto it = myMap.find(4);
if (it != myMap.end()) {
myMap.erase(it);
}

其他常用操作

size()：返回元素数量。
empty()：检查是否为空。
clear()：清空所有元素。
count(key)：返回键出现的次数（0 或 1）。

性能注意事项

map 的插入、删除和查找操作均为 O(log n)。若需更高性能且不要求顺序，可考虑 unordered_map（哈希表实现，平均 O(1) 时间复杂度）。

示例代码

#include <iostream>
#include <map>
#include <string>

int main() {
std::map<int, std::string> myMap = {{1, "apple"}, {2, "banana"}};
myMap[3] = "cherry";

for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

return 0;
}

C++ map 的基本概念

声明和初始化

使用 map 需要包含头文件 <map>，并通过模板参数指定键和值的类型：

#include <map>
std::map<int, std::string> myMap;

初始化方式包括直接赋值或列表初始化（C++11 及以上）：

std::map<int, std::string> myMap = {{1, "apple"}, {2, "banana"}};

插入元素

插入元素可以使用 insert 方法或 operator[]：

myMap.insert(std::make_pair(3, "cherry"));
myMap[4] = "date";

注意：operator[] 在键不存在时会自动创建新条目，而 insert 不会覆盖已存在的键。

访问元素

通过键访问值可以使用 operator[] 或 at 方法：

std::string fruit = myMap[1]; // 返回 "apple"
std::string fruit2 = myMap.at(2); // 返回 "banana"

at 方法在键不存在时会抛出 std::out_of_range 异常，而 operator[] 会插入默认值。

遍历元素

使用迭代器或范围循环（C++11 及以上）遍历 map：

for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

查找元素

使用 find 方法检查键是否存在：

auto it = myMap.find(3);
if (it != myMap.end()) {
std::cout << "Found: " << it->second << std::endl;
}

删除元素

通过键或迭代器删除元素：

myMap.erase(3); // 删除键为 3 的元素
auto it = myMap.find(4);
if (it != myMap.end()) {
myMap.erase(it);
}

其他常用操作

size()：返回元素数量。
empty()：检查是否为空。
clear()：清空所有元素。
count(key)：返回键出现的次数（0 或 1）。

性能注意事项

map 的插入、删除和查找操作均为 O(log n)。若需更高性能且不要求顺序，可考虑 unordered_map（哈希表实现，平均 O(1) 时间复杂度）。

示例代码

#include <iostream>
#include <map>
#include <string>

int main() {
std::map<int, std::string> myMap = {{1, "apple"}, {2, "banana"}};
myMap[3] = "cherry";

for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

return 0;
}

第二题：还是异或

题目描述

给定一个长度为 n 的序列 a1,a2,…,an。

对任意区间 [l,r]（1≤l≤r≤n），定义它的区间异或和为：

al⊕al+1⊕⋯⊕ar

请你统计有多少个区间的异或和恰好等于 k。

输入格式

第一行两个整数 n 和 k。
第二行 n 个整数 a1,a2,…,an。

输出格式

输出一个整数，表示满足条件的区间数量。

输入输出样例

输入 #1

3 0
1 2 3

输出 #1

输入 #2

3 1
1 2 3

输出 #2

输入 #3

3 0
0 0 0

输出 #3

输入 #4

6 7
7 0 7 7 0 7

输出 #4

说明/提示

对于样例 1：只有区间 [1,3] 的异或和为 1⊕2⊕3=0，因此答案为 1。

对于样例 2：满足条件的区间有 [1,1]（异或和为 1）与 [2,3]（2⊕3=1），共 2 个。

对于样例 3：任意区间的异或和都是 0。一共有 23×4=6 个区间，因此答案为 6。

数据范围：本题数据分布严格如下表所示：

数据占比约束条件

20%	1≤n≤103，0≤k,ai≤103
30%	1≤n≤105，0≤k,ai≤105
50%	1≤n≤105，0≤k,ai≤109

思路：

前缀异或和+map。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100100],d[100100];
long long ans;
map<long long ,long long> cnt;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
d[i]=d[i-1]^a[i];
}
cnt[0]=1;
for(int i=1;i<=n;i++){
ans+= cnt[k^d[i]];
cnt[d[i]]++;
}
cout<<ans;
return 0;
}

提高：

在C++中，std::map是标准模板库（STL）提供的关联容器，用于存储键值对（key-value pairs），并基于键自动排序。以下是关于std::map的详细说明和常见用法：

基本特性

有序性：std::map内部通常实现为红黑树，键值对按键的升序排列（默认使用std::less比较）。
唯一键：每个键在map中必须是唯一的，重复插入会覆盖原有值。
时间复杂度：插入、删除和查找操作的平均时间复杂度为O(log n)。

初始化与声明

#include <map>
#include <string>

std::map<int, std::string> myMap; // 键为int，值为string的空map
std::map<std::string, double> prices = {
{"apple", 1.99},
{"banana", 0.99}
}; // 初始化列表

常用操作

插入元素

myMap.insert(std::make_pair(1, "one")); // 使用insert
myMap[2] = "two"; // 使用operator[]，若键不存在则创建

访问元素

auto value = myMap[1]; // 通过键访问（若键不存在会插入默认值）
auto it = myMap.find(3); // 查找迭代器，返回end()表示未找到
if (it != myMap.end()) {
std::cout << it->second; // 输出值
}

删除元素

myMap.erase(1); // 通过键删除
auto it = myMap.find(2);
if (it != myMap.end()) {
myMap.erase(it); // 通过迭代器删除
}

遍历元素

for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

自定义排序规则

可以通过提供自定义比较函数或函数对象来改变排序规则：

struct CaseInsensitiveCompare {
bool operator()(const std::string& a, const std::string& b) const {
return std::lexicographical_compare(
a.begin(), a.end(), b.begin(), b.end(),
[](char c1, char c2) { return tolower(c1) < tolower(c2); }
);
}
};

std::map<std::string, int, CaseInsensitiveCompare> caseInsensitiveMap;

与unordered_map的区别

std::map保持有序，而std::unordered_map基于哈希表，无序但平均时间复杂度为O(1)。
需要有序遍历或自定义排序时选择map；追求性能且无需排序时选择unordered_map。

注意事项

使用operator[]访问不存在的键时会插入默认构造的值，可能引发意外行为。推荐先用find()检查。
迭代器在插入或删除操作后可能失效，需谨慎处理。

通过合理使用std::map，可以高效管理需要键值关联和排序的场景。

在C++中，std::map是标准模板库（STL）提供的关联容器，用于存储键值对（key-value pairs），并基于键自动排序。以下是关于std::map的详细说明和常见用法：

基本特性

有序性：std::map内部通常实现为红黑树，键值对按键的升序排列（默认使用std::less比较）。
唯一键：每个键在map中必须是唯一的，重复插入会覆盖原有值。
时间复杂度：插入、删除和查找操作的平均时间复杂度为O(log n)。

初始化与声明

#include <map>
#include <string>

std::map<int, std::string> myMap; // 键为int，值为string的空map
std::map<std::string, double> prices = {
{"apple", 1.99},
{"banana", 0.99}
}; // 初始化列表

常用操作

插入元素

myMap.insert(std::make_pair(1, "one")); // 使用insert
myMap[2] = "two"; // 使用operator[]，若键不存在则创建

访问元素

删除元素

myMap.erase(1); // 通过键删除
auto it = myMap.find(2);
if (it != myMap.end()) {
myMap.erase(it); // 通过迭代器删除
}

遍历元素

for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

自定义排序规则

可以通过提供自定义比较函数或函数对象来改变排序规则：

std::map<std::string, int, CaseInsensitiveCompare> caseInsensitiveMap;

与unordered_map的区别

std::map保持有序，而std::unordered_map基于哈希表，无序但平均时间复杂度为O(1)。
需要有序遍历或自定义排序时选择map；追求性能且无需排序时选择unordered_map。

注意事项

使用operator[]访问不存在的键时会插入默认构造的值，可能引发意外行为。推荐先用find()检查。
迭代器在插入或删除操作后可能失效，需谨慎处理。

通过合理使用std::map，可以高效管理需要键值关联和排序的场景。

第三题：会议中心

题目描述

有 n 个村庄排在一条数轴上，第 i 个村庄的位置为 ai（两两不同），该村庄有 bi 个人。

现在他们要集合开会，你需要选择一个会议点位置 x（x 为整数），使得所有人走的总路程最少。

总路程定义为：

i=1∑nbi⋅∣ai−x∣

请输出最小的总路程。

输入格式

第一行一个整数 n，表示村庄数量。

接下来 n 行，每行两个整数 ai,bi，分别表示村庄位置与该村庄的人数。

输出格式

输出一个整数，表示最小总路程。

输入输出样例

输入 #1复制

1
10 5

输出 #1复制

输入 #2复制

2
0 1
10 1

输出 #2复制

输入 #3复制

3
1 1
2 2
10 1

输出 #3复制

输入 #4复制

5
100 1
1 10
2 1
102 10
101 1

输出 #4复制

1109

说明/提示

对于样例 1：所有人都在同一个村庄，选 x=10 时总路程为 0。

对于样例 2：无论选 x=0 还是 x=10，总路程都是 10，因此答案为 10。

对于样例 3：选 x=2 时总路程为 1⋅∣1−2∣+2⋅∣2−2∣+1⋅∣10−2∣=1+0+8=9，这是最小值。

数据范围：本题数据分布严格如下表所示：

数据占比约束条件

30%	1≤n≤102，1≤ai,bi≤102
30%	1≤n≤103，1≤ai,bi≤105
40%	1≤n≤105，1≤ai,bi≤105

思路：

未完待续。

代码如下：

未完待续。

第四题：踩点

题目描述

你穿越到了古代，准备去劫狱，于是先到监狱旁边“踩点”。

你记录了每个守卫的上班与下班时间。把至少有一个守卫在岗的时间段视为“有人”，否则视为“没人”。

需要注意的是，你只统计从第一个守卫开始上班到最后一个守卫下班这段时间内的情况。
设

L=min(ai),R=max(bi)

则只在时间段 [L,R) 上讨论“有人/没人”，不考虑 L 之前或 R 之后的时间。

请你分别计算：

最长连续“没人”的时间长度；
最长连续“有人”的时间长度。

输入格式

第一行一个整数 n，表示守卫数量。
接下来 n 行，每行两个整数 ai,bi，表示第 i 个守卫的上班时间与下班时间（时间段为 [ai,bi)，即包含 ai 不包含 bi）。

输出格式

输出两个整数，用空格分隔，分别表示最长的“没人”时间长度与最长的“有人”时间长度。

输入输出样例

输入 #1复制

3
1 3
2 5
6 8

输出 #1复制

1 4

输入 #2复制

2
1 10
2 3

输出 #2复制

0 9

输入 #3复制

4
1 2
3 5
6 7
8 10

输出 #3复制

1 2

输入 #4复制

5
1 100
20 30
40 60
70 80
90 120

输出 #4复制

0 119

说明/提示

对于样例 1：“有人”的时间段是 [1,5) 与 [6,8)，中间空档 [5,6) 长度为 1；最长“有人”长度为 5−1=4。

对于样例 2：始终有人（因为 [1,10) 覆盖了全部），最长“没人”为 0，最长“有人”为 10−1=9。

对于样例 3：“有人”的时间段分别为 [1,2)、[3,5)、[6,7)、[8,10)，最长“没人”的空档长度为 1，最长“有人”长度为 2。

数据范围：本题数据分布严格如下表所示：

数据占比约束条件

20%	1≤n≤103，1≤ai<bi≤103
30%	1≤n≤105，1≤ai<bi≤105
50%	1≤n≤105，1≤ai<bi≤109

思路：

把那些重合时间点结合在一起。

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
int s,e;
};
node a[100001],b[100101];
int cmp(node n1,node n2){
if(n1.s!=n2.s) return n1.s<n2.s;
return n1.e<n2.e;
}
int main(){
long long n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].s>>a[i].e;
}
sort(a+1,a+1+n,cmp);
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i].s<=b[cnt].e){
b[cnt].e=max(b[cnt].e,a[i].e);
}
else{
b[++cnt]=a[i];
}
}
int ans1=0,ans2=b[1].e-b[1].s;
for(int i=2;i<=cnt;i++){
ans1=max(ans1,b[i].s-b[i-1].e);

ans2=max(ans2,b[i].e-b[i].s);
}
cout<<ans1<<' '<<ans2;
return 0;
}

第五题：构造字符串

题目描述

你需要构造一个长度为 n 的字符串，有以下限制：

只能使用大写字母 'X'、'Y'、'Z'；
'Y' 不能紧接在 'X' 后面（即不能出现子串 "XY"）；
'Z' 不能紧接在 'Y' 后面（即不能出现子串 "YZ"）。

请输出满足条件的字符串数量。由于方案数可能很大，请输出结果对 109+7 取模。

输入格式

输入一个整数 n。

输出格式

输出一个整数，表示答案对 109+7 取模后的结果。

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

输出 #2复制

输入 #3复制

输出 #3复制

输入 #4复制

输出 #4复制

1081

说明/提示

对于样例 1：长度为 1 时可以是 X、Y、Z，共 3 种。

对于样例 2：长度为 2 的所有字符串共 32=9 个，排除包含 "XY" 的 1 个（XY）和包含 "YZ" 的 1 个（YZ），剩下 7 种。

数据范围：本题数据分布严格如下表所示：

数据占比约束条件

30%	1≤n≤16
30%	1≤n≤103
30%	1≤n≤105
10%	1≤n≤1018

思路：

DP90分，要用矩阵快速幂。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,dp[100100][4];
struct node{
int a[4][4]={0};
};
node m(node n1,node n2){
node ans;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
ll tmp=0;
}
}
}
node q(node a,ll n){
node ans;
for(int i=1;i<4;i++){
ans.a[i][i];
}
while(n){
if(n%2) ans=m(ans,a);
n/=2;
a=m()
}
}
node s;ll n;
int main(){
cin>>n;
s.a[1][1]=s.a[1][2]=s.a[1][3]=s.a[2][2]=s.a[2][3]=s.a[3][1]=s.a[3][3]=1;

return 0;
}

提高：

矩阵快速幂的实现

矩阵快速幂是一种高效计算矩阵幂次的方法，适用于大指数情况。其核心思想是将幂次分解为二进制形式，通过分治策略降低时间复杂度至 (O(\\log n))。

矩阵定义与乘法

假设矩阵为 (n \\times n) 方阵，需先定义矩阵结构和乘法操作：

using Matrix = vector<vector<long long>>;

Matrix multiply(const Matrix &A, const Matrix &B, long long mod) {
int n = A.size();
Matrix result(n, vector<long long>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % mod;
}
}
}
return result;
}

快速幂核心算法

通过二进制分解指数，迭代计算矩阵幂：

Matrix matrix_pow(Matrix base, long long power, long long mod) {
int n = base.size();
Matrix result(n, vector<long long>(n, 0));
for (int i = 0; i < n; ++i) {
result[i][i] = 1; // 初始化为单位矩阵
}

while (power > 0) {
if (power & 1) {
result = multiply(result, base, mod);
}
base = multiply(base, base, mod);
power >>= 1;
}
return result;
}

使用示例

计算斐波那契数列第 (n) 项（模 (10^9+7)）：

long long fib(long long n, long long mod = 1e9 + 7) {
if (n <= 1) return n;
Matrix base = {{1, 1}, {1, 0}};
Matrix result = matrix_pow(base, n – 1, mod);
return result[0][0];
}

注意事项

矩阵乘法顺序：注意矩阵乘法的不可交换性，确保乘法顺序正确。
模数处理：大数运算时需及时取模，避免溢出。
单位矩阵初始化：快速幂开始时结果矩阵应初始化为单位矩阵。

该方法广泛应用于动态规划优化、图论路径计数等问题，尤其适合指数超过 (10^{18}) 的场景。

矩阵快速幂的实现

矩阵快速幂是一种高效计算矩阵幂次的方法，适用于大指数情况。其核心思想是将幂次分解为二进制形式，通过分治策略降低时间复杂度至 (O(\\log n))。

矩阵定义与乘法

假设矩阵为 (n \\times n) 方阵，需先定义矩阵结构和乘法操作：

using Matrix = vector<vector<long long>>;

快速幂核心算法

通过二进制分解指数，迭代计算矩阵幂：

while (power > 0) {
if (power & 1) {
result = multiply(result, base, mod);
}
base = multiply(base, base, mod);
power >>= 1;
}
return result;
}

使用示例

计算斐波那契数列第 (n) 项（模 (10^9+7)）：

long long fib(long long n, long long mod = 1e9 + 7) {
if (n <= 1) return n;
Matrix base = {{1, 1}, {1, 0}};
Matrix result = matrix_pow(base, n – 1, mod);
return result[0][0];
}

注意事项

矩阵乘法顺序：注意矩阵乘法的不可交换性，确保乘法顺序正确。
模数处理：大数运算时需及时取模，避免溢出。
单位矩阵初始化：快速幂开始时结果矩阵应初始化为单位矩阵。

该方法广泛应用于动态规划优化、图论路径计数等问题，尤其适合指数超过 (10^{18}) 的场景。

第六题：认祖归宗

题目描述

有 n 个人，编号为 1 到 n。除了一位“始祖”以外，每个人都只记得自己的父亲是谁。

你需要回答 m 次询问。每次给出两个人 p,q，请输出他们的最近共同祖先（也就是两人共同祖先中，离他们最近的那一位）。

输入格式

第一行两个整数 n,m，分别表示人数与询问数量。
接下来 n−1 行，每行两个整数 ai,bi，表示 ai 的父亲是 bi。
接下来 m 行，每行两个整数 pi,qi，表示一次询问。

输出格式

输出m行，每行表示一个祖宗

输入输出样例

输入 #1复制

5 3
2 1
3 1
4 2
5 2
4 5
4 3
2 3

输出 #1复制

2
1
1

输入 #2复制

1 2
1 1
1 1

输出 #2复制

1
1

输入 #3复制

6 3
2 1
3 2
4 3
5 4
6 5
2 6
3 6
1 6

输出 #3复制

2
3
1

说明/提示

对于样例 1：关系为 1 是 2,3 的父亲，2 是 4,5 的父亲。

询问 (4,5)：共同祖先有 2,1，最近的是 2；
询问 (4,3)：最近共同祖先是 1；
询问 (2,3)：最近共同祖先也是 1。

对于样例 2：只有 1 个人，任何询问的答案都是 1。

数据范围：本题数据分布严格如下表所示：

数据占比约束条件

40%	1≤n,m≤103
30%	1≤n,m≤105 且没人有相同的父亲
30%	1≤n,m≤105

思路：

其实样例不强，暴力LCA就能过

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[101000],d[101001],v=1;
int lca(int p,int q){
if(p==q) return p;
if(p>q){
return lca(fa[p],q);
}
return lca(p,fa[q]);
}
int main(){
cin>>n>>m;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
fa[x]=y;
d[y]++;
}
for(int i=1;i<=n;i++){
if(d[i]>1) v=0;
}
if(v){
for(int i=1;i<=m;i++){
int s,d;
cin>>s>>d;
cout<<min(s,d)<<endl;
}
return 0;
}
for(int i=1;i<=m;i++){
int s,d;
cin>>s>>d;
cout<<lca(s,d)<<endl;
}
return 0;
}

提高：

C++ 实现最近公共祖先（LCA）

最近公共祖先（Lowest Common Ancestor, LCA）是树结构中两个节点的最低层公共祖先节点。以下是几种常见实现方法：

方法一：递归法（适用于二叉树）

假设树节点结构如下：

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};

递归实现代码：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return !left ? right : (!right ? left : root);
}

方法二：迭代法（使用父指针）

适用于通用树结构，需要先构建父指针映射：

unordered_map<TreeNode*, TreeNode*> parent;
void buildParentMap(TreeNode* root) {
if (!root) return;
if (root->left) {
parent[root->left] = root;
buildParentMap(root->left);
}
if (root->right) {
parent[root->right] = root;
buildParentMap(root->right);
}
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
buildParentMap(root);
unordered_set<TreeNode*> ancestors;
while (p) {
ancestors.insert(p);
p = parent[p];
}
while (q) {
if (ancestors.count(q)) return q;
q = parent[q];
}
return nullptr;
}

方法三：二进制提升法（适用于多次查询）

预处理每个节点的2^k级祖先，适合处理大量查询：

const int LOG = 20;
vector<vector<int>> up;
vector<int> depth;

void dfs(int u, int p, vector<vector<int>>& adj) {
up[u][0] = p;
for (int i = 1; i < LOG; ++i)
up[u][i] = up[up[u][i-1]][i-1];
for (int v : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u, adj);
}
}
}

int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG-1; i >= 0; –i) {
if (depth[u] – (1 << i) >= depth[v]) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = LOG-1; i >= 0; –i) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}

注意事项

递归法时间复杂度O(n)，适合一次性查询

二进制提升法预处理O(n log n)，查询O(log n)，适合多次查询

对于非二叉树，需要调整遍历逻辑

实际应用中需考虑节点不存在等边界条件