暴龙
题目背景
Hanghang 红温了，然后他变异成了暴龙。
题目描述
机房里有 k 种暴龙。现在他们占据了一棵树上的所有的点。这棵树有 n 个点，边有边权。现在对于某一种暴龙，他们的红温值定义为任意两个这种暴龙的距离的最大值。如果这种暴龙的出现次数小于 2，则红温值为 0。考拉想要证明 Hanghang 红温了，因此他想要问你每种暴龙的红温值。
输入格式
第一行两个正整数 n,k，表示树的节点数和暴龙的种类数。
第二行 n 个在 [1,k] 间的正整数 p_i，表示每个节点的暴龙的种类。
接下来 n-1 行，每行三个正整数 a,b,c，表示 a,b 之间有一条边，边权为 c。保证这些边构成一棵树。
输出格式
输出 k 行，每行一个数表示种类为 i 的暴龙的红温值。
样例 #1
样例输入 #1
6 3
2 3 1 1 2 3
1 2 1
1 3 1
2 5 1
3 4 1
3 6 1
样例输出 #1
1
2
3
提示
【样例 2】
见选手目录下的 tree/tree2.in 与 tree/tree2.ans。
该样例满足子任务 1 的限制。
【样例 3】
见选手目录下的 tree/tree3.in 与 tree/tree3.ans。
该样例满足子任务 2 的限制。
【样例 4】
见选手目录下的 tree/tree4.in 与 tree/tree4.ans。
该样例满足子任务 3 的限制。
【样例 5】
见选手目录下的 tree/tree5.in 与 tree/tree5.ans。
该样例满足子任务 4 的限制。
本题使用捆绑测试。
| 子任务编号 | n | 分值 |
|---|---|---|
| 1 | 3000 | 5 |
| 2 | 10^5 | 10 |
| 3 | 3\times 10^5 | 10 |
| 4 | 5\times 10^5 | 75 |
对于所有数据，1\leq p_i \leq k\leq n\leq 5\times 10^5,1\leq a,b\leq n,1\leq c\leq 10^9。
本题输入输出量较大，请选手使用较快的 IO 方式。
本题下发文件：https://git.zziyu.cn/Zengtudor/algorithm_2024/src/branch/main/src/20241118/tree（打开后预览）
25pts暴力代码与解析
关于使用ai
- 下面的代码是本人手写，注释和解释由ai生成
- 解析由ai生成模型为chatgpt o1-mini
#include <cctype>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
#include <map>
using ll = int64_t;
using std::cin, std::cout;
// 定义最大节点数为5e5加5，以确保足够的空间
const ll maxn = 5e5 + 5;
ll n, k; // n: 树的节点数，k: 暴龙的种类数
ll a[maxn]; // a[i]: 第i个节点的暴龙种类
ll ans[maxn]; // ans[i]: 第i种暴龙的红温值
std::vector<std::pair<ll, ll>> adj[maxn]; // adj[u]: 节点u的邻居及边权
std::map<ll, ll> dp[maxn]; // dp[u][j]: 节点u到子树中种类j的最大距离
// 优化输入读取，提高IO速度
struct CinNum {
char c;
ll n, w;
// 重载右移运算符以自定义输入方式
CinNum &operator>>(ll &num) {
c = n = 0;
w = 1;
// 跳过非数字字符，记录负号
while (!isdigit(c = getchar())) {
if (c == '-') w = -1;
}
// 读取数字
while (isdigit(c)) {
n = n * 10 + (c - '0');
c = getchar();
}
num = n * w;
return *this;
}
} cinn;
// 使用自定义的CinNum来替代标准输入
#define cin cinn
/**
* @brief 使用深度优先搜索 (DFS) 计算每种暴龙的红温值
*
* @param fth 当前节点的父节点
* @param u 当前处理的节点
*/
void dfs(const ll &fth, const ll &u) noexcept {
// 初始化当前节点的dp，自己到自己距离为0
dp[u].emplace(a[u], 0);
// 遍历所有邻接节点
for (const auto& [v, w] : adj[u]) {
if (v == fth) continue; // 避免回到父节点
dfs(u, v); // 递归处理子节点
// 遍历子节点v的所有暴龙种类及其对应的最大距离
for (const auto& [kk, vv] : dp[v]) {
// 如果当前节点u已经有这种暴龙类型，且子节点v也有
if ((dp[u][kk] > 0 || a[u] == kk) && (dp[v][kk] > 0 || a[v] == kk)) {
// 更新ans[kk]为u和v子树中这种暴龙类型的最大距离
ans[kk] = std::max(ans[kk], dp[u][kk] + dp[v][kk] + w);
}
// 更新u节点到这种暴龙类型的最大距离
dp[u][kk] = std::max(dp[u][kk], dp[v][kk] + w);
// 如果当前节点u本身就是这种暴龙类型，进一步更新ans[kk]
if (a[u] == kk) {
ans[kk] = std::max(ans[kk], dp[u][kk]);
}
}
// 清空子节点v的dp以节省内存，因为已经合并到u的dp中了
dp[v].clear();
}
}
int main(){
// 读取节点数n和暴龙种类数k
cin >> n >> k;
// 读取每个节点的暴龙种类
for(ll i = 1; i <= n; i++) cin >> a[i];
// 读取树的边信息，并构建邻接表
for(ll i = 1; i < n; i++){
ll u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
// 从节点1开始DFS遍历整棵树，假设节点1为根节点，父节点为0
dfs(0, 1);
// 输出每种暴龙的红温值
for(ll i = 1; i <= k; i++) cout << ans[i] << '\n';
}
代码详解
-
数据结构选择:
- 邻接表: 使用
std::vector<std::pair<ll, ll>> adj[maxn];来存储树的邻接表，每个节点存储与之相连的节点及边权。 - 动态规划表（DP）: 使用
std::map<ll, ll> dp[maxn];来存储每个节点到其子树中不同暴龙种类的最大距离。这里使用std::map是因为暴龙种类k可能较多且不连续。
- 邻接表: 使用
-
输入优化:
- 定义了一个自定义的
CinNum结构体，通过重载>>运算符来快速读取整数。这在处理大数据量时能够显著提高输入速度。
- 定义了一个自定义的
-
深度优先搜索（DFS）:
- 初始化: 对于每个节点u，将自己的暴龙种类
a[u]加入dp[u]，初始距离为0。 - 递归处理子节点: 对每个子节点v，递归调用
dfs(u, v)。 - 合并子节点DP: 对于子节点v的每个暴龙种类kk，检查当前节点u是否也有这种暴龙。如果有，则计算通过边(u, v)连接后的距离，并更新
ans[kk]为更大的值。 - 更新u节点的DP: 将子节点v的距离加上边权w，与当前的
dp[u][kk]比较，取较大者。 - 清理资源: 处理完子节点v后，清空
dp[v]以节省内存。
- 初始化: 对于每个节点u，将自己的暴龙种类
-
输出结果:
- 遍历每种暴龙种类，输出其对应的红温值。若某种暴龙在树中数量少于2，则红温值保持初始化的0。
总结
该算法利用深度优先搜索（DFS）结合动态规划（DP）的思想，高效地计算了树中每种暴龙类型的最大距离（红温值）。具体步骤如下：
- DFS遍历: 从根节点开始，递归遍历整个树结构。
- 动态规划: 在遍历的过程中，维护每个节点到其子树中特定暴龙类型的最大距离。
- 答案更新: 通过合并子节点的信息，动态地更新每种暴龙类型的最大距离。
- 复杂度分析:
- 对于每个节点，可能需要处理最多k种暴龙类型。因此，时间复杂度在最坏情况下为O(nk)。由于k和n均可达5e5，这种方法在大规模数据下会超过时间限制。
- 适用性:
- 该代码适用于子任务1，规模较小（n ≤ 3000）的情况，能够在有限的时间内完成计算。
- 对于更大规模的数据，需要优化数据结构和算法，例如使用更高效的方式存储DP信息（如并查集、最低公共祖先LCA等技术），以降低时间和空间复杂度。
希望这些解释和注释对您理解和优化代码有所帮助！如果有进一步的问题，欢迎继续交流。
100pts解
题目概述
本题涉及在一棵带权树上计算不同类型的暴龙（类似于节点类型）的红温值（即同类型暴龙任意两点之间的最大距离）。具体来说，给定一棵有 n 个节点和边权的树，树上的每个节点都有 k 种暴龙中的一种。对于每一种暴龙类型，定义其红温值为同类型暴龙之间的最大距离；如果该类型的暴龙数量小于2，则红温值为0。
解题思路
-
树的预处理：
- 深度优先搜索 (DFS)：计算每个节点的深度 (
dpt)，以及从根节点到该节点的距离 (w)。 - 二进制跳表 (Binary Lifting)：预处理每个节点的祖先节点，以便快速计算任意两个节点的最近公共祖先 (LCA)。
- 距离计算：利用 LCA，计算任意两个节点之间的距离。
- 深度优先搜索 (DFS)：计算每个节点的深度 (
-
计算每种暴龙的红温值：
- 对于每种暴龙类型，首先选取其中任意两个节点，计算它们之间的距离作为初始的最大距离 (
ans)。 - 逐一遍历该类型的所有节点，对于每个新的节点，计算它与当前两个端点的距离，更新端点和
ans的值以确保ans始终为当前类型的最大距离。
- 对于每种暴龙类型，首先选取其中任意两个节点，计算它们之间的距离作为初始的最大距离 (
代码详解与注释
#include <cstdint>
#include <iostream>
#include <vector>
#include <bitset>
// 使用类型别名提高代码可读性
using ll = int64_t;
using std::cin, std::cout;
// 常量定义
const ll maxn = 5e5 + 5; // 最大节点数
const ll L = 20; // 二进制跳表的层数，满足 n <= 5e5 时 2^20 > 5e5
// 全局变量
ll n, k; // 节点数和暴龙种类数
ll a[maxn]; // a[i] 表示节点 i 的暴龙类型
ll fa[maxn][L]; // fa[u][j] 表示节点 u 的 2^j 祖先节点
ll dpt[maxn]; // dpt[u] 表示节点 u 的深度
ll w[maxn]; // w[u] 表示节点 u 与根节点的距离
std::vector<ll> g[maxn]; // g[i] 存储所有类型为 i 的节点
std::vector<std::pair<ll, ll>> adj[maxn]; // adj[u] 存储节点 u 的所有邻接点及对应边权
// DFS 预处理，计算深度和从根到每个节点的距离
void dfs(const ll &fth, const ll &u){
fa[u][0] = fth; // 记录节点 u 的直接父节点
for(auto& [v, ww] : adj[u]){
if(v == fth) continue; // 避免回到父节点
dpt[v] = dpt[u] + 1; // 更新子节点的深度
w[v] = w[u] + ww; // 更新子节点到根的距离
dfs(u, v); // 递归遍历子节点
}
}
// 初始化二进制跳表，用于快速查询 LCA
void initfa(){
for(ll j = 1; j < L; j++){ // 对于每一层
for(ll u = 1; u <= n; u++){ // 对于每个节点
fa[u][j] = fa[fa[u][j-1]][j-1]; // 2^j 祖先等于 2^(j-1) 的祖先的 2^(j-1) 祖先
}
}
}
// 计算两个节点的最近公共祖先 (LCA)
ll lca(ll u, ll v){
if(dpt[u] < dpt[v]) std::swap(u, v); // 确保 u 的深度不小于 v
ll dif = dpt[u] - dpt[v];
// 将 u 提升到与 v 在同一深度
for(ll j = 0; dif > 0; j++, dif >>= 1){
if(dif & 1){
u = fa[u][j];
}
}
if(u == v) return u; // 如果 v 是 u 的祖先，直接返回
// 从高位到低位同时提升 u 和 v，找到 LCA
for(ll j = L-1; j >= 0; j--){
if(fa[u][j] != fa[v][j]){
u = fa[u][j];
v = fa[v][j];
}
}
return fa[u][0]; // 返回 LCA
}
// 计算两个节点之间的距离
ll dis(const ll &u, const ll &v){
return w[u] + w[v] - 2 * w[lca(u, v)];
}
int main(){
// 关闭同步，提高输入输出速度
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
// 输入节点数和暴龙种类数
cin >> n >> k;
// 输入每个节点的暴龙类型，并将节点编号加入对应类型的列表
for(ll i = 1; i <= n; i++){
cin >> a[i];
g[a[i]].push_back(i);
}
// 输入树的边
for(ll i = 1; i < n; i++){
ll u, v, c;
cin >> u >> v >> c;
adj[u].emplace_back(v, c);
adj[v].emplace_back(u, c);
}
// 从根节点 1 开始进行 DFS 预处理
dfs(0, 1);
// 初始化二进制跳表
initfa();
// 对于每一种暴龙类型，计算其红温值
for(ll i = 1; i <= k; i++){
// 如果该类型的暴龙数量小于2，红温值为0
if(g[i].size() < 2){
cout << "0\n";
continue;
}
// 初始化第一个端点 u 和第二个端点 v
ll u = g[i][0];
ll v = g[i][1];
// 计算初始的最大距离
ll ans = dis(u, v);
// 遍历该类型的剩余节点，更新端点和最大距离
for(ll j = 2; j < (ll)g[i].size(); j++){
ll du = dis(u, g[i][j]); // 当前节点与端点 u 的距离
ll dv = dis(v, g[i][j]); // 当前节点与端点 v 的距离
if(du > dv){
if(du > ans){
v = g[i][j]; // 更新 v 为当前节点
ans = du; // 更新最大距离
}
}
else{
if(dv > ans){
u = g[i][j]; // 更新 u 为当前节点
ans = dv; // 更新最大距离
}
}
}
// 输出该类型的红温值
cout << ans << '\n';
}
}
详细解释
-
输入与预处理：
- 节点信息：首先读取节点数
n和暴龙种类数k。然后读取每个节点的暴龙类型，存储在数组a中，并将每个节点编号加入对应类型的列表g[i]。 - 树的构建：接下来读取
n-1条边，每条边连接两个节点并有一个边权，将这些信息存储在邻接表adj中。
- 节点信息：首先读取节点数
-
深度优先搜索 (DFS) 和二进制跳表初始化：
- DFS：从根节点（这里假设为节点1）开始遍历整棵树，计算每个节点的深度
dpt，以及从根节点到该节点的距离w。同时，记录每个节点的直接父节点fa[u][0]。 - 二进制跳表 (
initfa函数)：构建一个fa数组，其中fa[u][j]表示节点u的2^j祖先节点。通过动态规划的方式，fa[u][j] = fa[fa[u][j-1]][j-1]，从而可以在对数时间内找到任意节点的祖先，用于高效计算 LCA。
- DFS：从根节点（这里假设为节点1）开始遍历整棵树，计算每个节点的深度
-
最近公共祖先 (LCA) 和距离计算：
- LCA (
lca函数)：利用二进制跳表，首先将深度较深的节点提升到与另一个节点同一深度，然后同时提升两者直到找到 LCA。 - 距离 (
dis函数)：利用 LCA 计算两个节点之间的距离，即w[u] + w[v] - 2*w[lca(u, v)]。
- LCA (
-
计算每种暴龙的红温值：
- 对于每种暴龙类型
i：- 如果该类型的节点数少于2，输出0。
- 否则，选择该类型中的任意两个节点作为初始的两个端点
u和v，计算它们之间的距离作为初始的红温值ans。 - 遍历该类型的剩余节点，每遇到一个新节点，计算它与当前两个端点的距离
du和dv。- 如果
du > dv：- 如果
du > ans，则将端点v更新为当前节点，ans更新为du。
- 如果
- 否则：
- 如果
dv > ans，则将端点u更新为当前节点，ans更新为dv。
- 如果
- 如果
- 这种方法类似于在树上寻找直径的双 BFS 方法，通过两次遍历找到最大距离。
- 对于每种暴龙类型
-
输出结果：
- 对每一种暴龙类型，输出其对应的红温值。
算法复杂度分析
-
预处理阶段：
- DFS：O(n)。
- 二进制跳表初始化：O(n \log n)。
-
每种类型的红温值计算：
- 对于每种类型，遍历其所有节点，计算距离。
- 总体复杂度为 O(k \cdot m \cdot \log n)，其中 m 是每种类型的节点数。
-
整体复杂度：由于 k \leq n 且每种类型的节点总和为 n，整体复杂度为 O(n \log n + n \log n) = O(n \log n)，满足题目约束。
代码优化技巧
- 高效输入输出：使用
std::ios::sync_with_stdio(false)和std::cin.tie(nullptr)关闭同步和绑定，提高输入输出速度，避免因大量数据导致超时。 - 使用静态数组：利用预定义大小的静态数组（如
a[maxn],fa[maxn][L]等）提高访问速度和内存利用效率。 - 按类型存储节点：将相同类型的节点集中存储在
g[i]中，便于后续遍历和计算。
总结
本题通过有效地预处理树的深度、距离和 LCA，结合类似于双 BFS 的方法，能够在较低的时间复杂度内求解每一种暴龙类型的红温值。关键在于利用二进制跳表实现高效的 LCA 查询，以及聪明地遍历节点以找到最大距离。这种方法在处理大规模树型数据时尤为有效，适用于类似的树上最远点对问题。
详细解释 LCA（最近公共祖先）与二进制位的关系
在树结构中，最近公共祖先（Lowest Common Ancestor, LCA） 是指两个节点在树中共同的最深的祖先节点。高效地计算 LCA 对于许多树相关的问题至关重要，例如本题中用于计算节点间距离。
本文将详细解释如何利用 二进制提升（Binary Lifting） 技术来高效计算 LCA，特别是如何通过二进制位的概念实现这一过程。
二进制提升概述
二进制提升 是一种预处理技术，用于在树上快速查询任意两个节点的 LCA。其核心思想是为每个节点预计算并存储其 2^j 祖先节点，其中 j 从 0 到 log₂n。这允许我们以对数时间复杂度（O(log n)）跳跃树的高度，从而快速找到 LCA。
关键概念
-
2^j 祖先节点（fa[u][j]）：
- 对于树中的每个节点 u 和每个 j（0 ≤ j ≤ log₂n），fa[u][j] 表示节点 u 的第 2^j 级祖先节点。
- 例如，fa[u][0] 是 u 的直接父节点，fa[u][1] 是 u 的祖父节点（2^1 = 2 跳），fa[u][2] 是 u 的曾祖父节点（2^2 = 4 跳），依此类推。
-
节点深度（dpt）：
- dpt[u] 表示节点 u 相对于根节点的深度（根节点深度为 0）。
-
距离表示与二进制位：
- 任意整数可以用二进制表示为若干个 2^j 的和。例如，13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0，对应二进制 1101。
- 这种表示方式允许我们通过二进制位选择性地跳跃若干步，从而高效地移动节点。
计算 LCA 的步骤与二进制位的应用
以下为计算两个节点 u 和 v 的 LCA 的主要步骤，详细解释了二进制位的应用：
-
确保 u 在较深的位置：
if(dpt[u] < dpt[v]) std::swap(u, v);确保节点 u 比节点 v 深，这样我们只需处理 u 的提升。
-
计算深度差并用二进制表示：
ll dif = dpt[u] - dpt[v];计算节点 u 和节点 v 之间的深度差 dif。
-
将 u 提升到与 v 同一深度：
for(ll j = 0; dif > 0; j++, dif >>= 1){ if(dif & 1){ u = fa[u][j]; } }- 二进制位检查：通过检查 dif 的每一位（从低到高），确定需要提升的步数。
- 位的意义：每一位 j（从 0 开始）对应着 2^j 步的提升。
- 示例：
- 若 dif = 13（即二进制 1101），则表示需要提升 2^0 + 2^2 + 2^3 = 1 + 4 + 8 = 13 步。
- 循环过程中：
- j=0: dif & 1 = 1，提升 2^0 = 1 步，u = fa[u][0]
- j=1: dif >> 1 = 6，dif & 1 = 0，跳过
- j=2: dif >> 2 = 3，dif & 1 = 1，提升 2^2 = 4 步，u = fa[u][2]
- j=3: dif >> 3 = 1，dif & 1 = 1，提升 2^3 = 8 步，u = fa[u][3]
- 最终，u 被提升 13 步，达到与 v 同一深度。
-
检查是否已经找到 LCA：
if(u == v) return u;如果提升后 u 和 v 重合，则 LCA 为 u（或 v）。
-
同步提升 u 和 v 以找到 LCA：
for(ll j = L - 1; j >= 0; j--){ if(fa[u][j] != fa[v][j]){ u = fa[u][j]; v = fa[v][j]; } } return fa[u][0];- 从高位到低位：从最大的 j 开始，逐步检查并提升 u 和 v。
- 条件判断：若 fa[u][j] != fa[v][j]，则同时提升 u 和 v 到它们各自的第 2^j 祖先。
- 找到 LCA：最终，u 和 v 的父节点（fa[u][0]）为 LCA。
二进制位的应用：
- 通过从高到低的二进制位检查，我们确保每一步尽可能多地提升 u 和 v，快速缩小它们的差距。
- 这种方式最大限度地利用了二进制表示中的高位，从而在对数步内完成提升，达到高效计算的目的。
示例说明
让我们通过一个具体示例来说明二进制位在 LCA 计算中的应用。
示例树结构：
1
/ \
2 3
/ / \
4 5 6
/ \
7 8
节点深度（dpt）与 fa 表：
| 节点 | dpt | fa[u][0] | fa[u][1] | fa[u][2] | fa[u][3] |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 0 | 0 |
| 4 | 2 | 2 | 1 | 0 | 0 |
| 5 | 2 | 3 | 1 | 0 | 0 |
| 6 | 2 | 3 | 1 | 0 | 0 |
| 7 | 3 | 4 | 2 | 1 | 0 |
| 8 | 3 | 4 | 2 | 1 | 0 |
查询 LCA(7, 5)：
-
节点深度：
- dpt[7] = 3
- dpt[5] = 2
-
保证 u 深度 >= v 深度：
- u = 7, v = 5
-
计算深度差 dif = 3 - 2 = 1（二进制 0001）：
- 0001 表示需要提升 2^0 = 1 步。
-
提升 u 7 一步：
- fa[7][0] = 4 → u = 4
-
比较 u 和 v：
- u = 4, v = 5
- u ≠ v，因此需要继续提升。
-
同步提升 u 和 v：
- 从 j = L-1（假设 L=4）到 j=0：
- j=3 到 j=2：fa[4][3] = 0, fa[5][3] = 0 → 相等，跳过
- j=1：
- fa[4][1] = 1
- fa[5][1] = 1
- 相等，跳过
- j=0：
- fa[4][0] = 2
- fa[5][0] = 3
- 不相等，提升：
- u = fa[4][0] = 2
- v = fa[5][0] = 3
- 从 j = L-1（假设 L=4）到 j=0：
-
找到 LCA：
- 最终，u = 2，v = 3
- fa[2][0] = 1
- fa[3][0] = 1
- LCA = 1
总结：LCA(7,5) = 1
二进制位在代码中的应用
让我们回顾代码中 LCA 相关部分，并结合上述示例进一步理解。
ll lca(ll u, ll v){
if(dpt[u] < dpt[v]){
std::swap(u, v);
}
ll dif = dpt[u] - dpt[v];
// 将 u 提升到与 v 同一深度
for(ll j = 0; dif > 0; j++, dif >>= 1){
if(dif & 1){
u = fa[u][j];
}
}
if(u == v){
return u;
}
// 同时提升 u 和 v 直到它们的父节点相同
for(ll j = L-1; j >= 0; j--){
if(fa[u][j] != fa[v][j]){
u = fa[u][j];
v = fa[v][j];
}
}
return fa[u][0];
}
详细解释：
-
提升 u 到 v 的深度：
- 通过检查 dif 的每一位（即二进制位），决定是否需要进行 2^j 次提升。
- 如果 dif 的某一位为 1，则将 u 提升 2^j 步。
-
同步提升 u 和 v：
- 从最高的二进制位（L-1）开始，逐步检查并提升 u 和 v。
- 若 fa[u][j] != fa[v][j]，则将 u 和 v 分别提升 2^j 步，直到它们接近 LCA。
-
返回 LCA：
- 最终，fa[u][0] 即为 LCA。
二进制位与跳跃步数的对应关系
- 每一位 j（从 0 开始）对应着 2^j 的跳跃步数。
- 通过位操作，可以将任意步数的提升分解为若干个 2^j 的跳跃，从而高效实现多级提升。
具体对应关系：
| j（位数） | 2^j（跳跃步数） |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| ... | ... |
| L-1 | 2^(L-1) |
举例说明：
假设需要提升一个节点 u 13 步：
- 13 的二进制表示为 1101。
- 这意味着需要：
- 2^0 = 1 步（j=0）
- 2^2 = 4 步（j=2）
- 2^3 = 8 步（j=3）
- 通过分别提升 u 一步、四步和八步，总共提升13步。
在代码中，这通过以下操作实现：
for(ll j = 0; dif > 0; j++, dif >>= 1){
if(dif & 1){
u = fa[u][j];
}
}
- 每次循环检查 dif 的最低位（dif & 1）。
- 若为1，则将 u 提升 2^j 步，即 u = fa[u][j]。
- 然后，将 dif 右移一位（dif >>= 1），准备检查下一位。
为什么二进制提升高效？
- 时间复杂度：计算 LCA 的时间复杂度为 O(log n)，因为提升和同步提升均涉及对数级别的操作。
- 空间复杂度：需要 O(n log n) 的空间来存储 fa 表，但这对于 n ≤ 5×10^5 是可接受的。
相比于传统的每次向上遍历节点的方式（可能达到 O(n) 的时间复杂度），二进制提升显著提高了效率，特别是在处理大规模数据时。
总结
在本题中，二进制提升 技术通过预计算每个节点的 2^j 祖先，结合二进制位的表示，能够在对数时间内高效地计算树中任意两个节点的 LCA。这种方法的核心在于利用二进制位对应的跳跃步数，实现快速的多级提升，从而优化查询效率。理解并掌握二进制提升对于解决大规模树问题（如本题）具有重要意义。
