【2024蓝桥杯/C++/A组/零食采购】

题目

方法

最近公共祖先lca的倍增算法binary lifting

深度优先搜索

二进制模拟

代码

#include<bits/stdc++.h>
using namespace std;// 定义常量N
const int N = 1e5+10;// 边的集合
vector<int> edge[N];
// 每个节点对应的数值
int num[N];
// 父节点数组，fa[i][j][0]表示节点i在第2^j层的父节点，fa[i][j][1]表示从i到2^j层父节点的路径上种类二进制数
int fa[N][25][2];
// 节点的深度
int d[N];
// 输入的节点数和查询次数
int n, q;// 深度优先搜索，初始化每个节点的深度和第一个父节点信息
void dfs(int from, int u)
{d[u] = d[from]+1;fa[u][0][0] = from;fa[u][0][1] = num[from];for(auto to : edge[u]){if(to == from) continue;dfs(u, to);}
}
// 初始化所有节点的父节点信息
void init()
{// 从2^1层到2^20层for(int i = 1; i < 20; i++){// 对每个节点进行处理for(int j = 1; j <= n; j++){// 找到当前节点j的2^i层父节点，即其2^(i-1)层父节点的2^(i-1)层父节点fa[j][i][0] = fa[fa[j][i-1][0]][i-1][0]; // 将从j到2^i层父节点的路径上的数值或运算结果计算出来，即先到2^(i-1)层父节点，再继续到2^i层父节点fa[j][i][1] = fa[j][i-1][1] | fa[fa[j][i-1][0]][i-1][1]; }}
}
// 计算一个整数中1的个数
int cnt(int x)
{int result = 0;while(x){if(x & 1) result++;x >>= 1;}return result;
}
// 最近公共祖先算法实现，返回从节点a到节点b路径上的数值或运算结果中1的个数
int lca(int a, int b)
{int tmp = num[a] | num[b];if(d[a] < d[b])  swap(a, b);// 让a和b处于同一深度for(int i = 19; i >= 0; i--){if(d[fa[a][i][0]] >= d[b]) //a始终比b深或者刚好一样深{tmp |= fa[a][i][1];a = fa[a][i][0];}}// 如果此时a和b相同，则直接返回tmp中1的个数if(a == b) return cnt(tmp);// 如果ab某一父节点不同，跳至，退出时父节点应一致for(int i = 19; i >= 0; i--){if(fa[a][i][0] != fa[b][i][0]) //父节点不同{tmp |= fa[a][i][1];tmp |= fa[b][i][1];a = fa[a][i][0];b = fa[b][i][0];}}tmp |= fa[a][0][1]; //纳入父节点的种类return cnt(tmp);
}
// 主函数
int main()
{// 输入节点数n和查询次数qcin >> n >> q;// 输入每个节点对应的数值，并将其转换为对应位置的二进制位设置为1for(int i = 1; i <= n; i++){int t;cin >> t;num[i] = 1 << (t-1);}// 构建树结构for(int i = 1; i < n; i++){int from, to;cin >> from >> to;edge[from].push_back(to);edge[to].push_back(from);}// 初始化每个节点的深度和第一个父节点信息dfs(0, 1);// 初始化所有节点的父节点信息init();// 处理查询for(int i = 1; i <= q; i++){int from, to;cin >> from >> to;cout << lca(from, to) << endl;}return 0;
}