本文涉及知识点
树上倍增
P9245 [蓝桥杯 2023 省 B] 景区导游
题目描述
某景区一共有 N N N 个景点，编号 1 1 1 到 N N N。景点之间共有 N − 1 N-1 N−1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K K K 个景点： A 1 , A 2 , … , A K A_{1},A_{2},\ldots,A_{K} A1,A2,…,AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 K-1 K−1 个景点。具体来说，如果小明选择跳过 A i A_{i} Ai，那么他会按顺序带游客游览 A 1 , A 2 , … , A i − 1 , A i + 1 , … , A K ( 1 ≤ i ≤ K ) A_{1},A_{2},\ldots,A_{i-1},A_{i+1},\ldots,A_{K}(1 \leq i \leq K) A1,A2,…,Ai−1,Ai+1,…,AK(1≤i≤K)。
请你对任意一个 A i A_{i} Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？
输入格式
第一行包含 2 2 2 个整数 N N N 和 K K K。
以下 N − 1 N-1 N−1 行，每行包含 3 3 3 个整数 u ， v , t u，v, t u，v,t，代表景点 u u u 和 v v v 之间有摆渡车线路，花费 t t t 个单位时间。
最后一行包含 K K K 个整数 A 1 , A 2 , … , A K A_{1},A_{2},\ldots,A_{K} A1,A2,…,AK 代表原定游览线路。
输出格式
输出 K K K 个整数，其中第 i i i 个代表跳过 A i A_{i} Ai 之后，花费在摆渡车上的时间。
输入输出样例 #1
输入 #1
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1
输出 #1
10 7 13 14
说明/提示
【样例说明】
原路线是 2 → 6 → 5 → 1 2 \rightarrow 6 \rightarrow 5 \rightarrow 1 2→6→5→1。
当跳过 2 2 2 时，路线是 6 → 5 → 1 6 \rightarrow 5 \rightarrow 1 6→5→1，其中 6 → 5 6 \rightarrow 5 6→5 花费时间 3 + 2 + 2 = 7 3+2+2=7 3+2+2=7， 5 → 1 5 \rightarrow 1 5→1 花费时间 2 + 1 = 3 2+1=3 2+1=3，总时间花费 10 10 10。
当跳过 6 6 6 时，路线是 2 → 5 → 1 2 \rightarrow 5 \rightarrow 1 2→5→1，其中 2 → 5 2 \rightarrow 5 2→5 花费时间 1 + 1 + 2 = 4 1+1+2=4 1+1+2=4， 5 → 1 5 \rightarrow 1 5→1 花费时间 2 + 1 = 3 2+1=3 2+1=3，总时间花费 7 7 7。
当跳过 5 5 5 时，路线是 2 → 6 → 1 2 \rightarrow 6 \rightarrow 1 2→6→1，其中 2 → 6 2 \rightarrow 6 2→6 花费时间 1 + 1 + 2 + 3 = 7 1+1+2+3=7 1+1+2+3=7， 6 → 1 6 \rightarrow 1 6→1 花费时间 3 + 2 + 1 = 6 3+2+1=6 3+2+1=6 ，总时间花费 13 13 13。
当跳过 1 1 1 时，路线时 2 → 6 → 5 2 \rightarrow 6 \rightarrow 5 2→6→5，其中 2 → 6 2 \rightarrow 6 2→6 花费时间 1 + 1 + 2 + 3 = 7 1+1+2+3=7 1+1+2+3=7， 6 → 5 6 \rightarrow 5 6→5 花费时间 3 + 2 + 2 = 7 3+2+2=7 3+2+2=7 ，总时间花费 14 14 14。
【评测用例规模与约定】
对于 20 % 20 \% 20% 的数据， 2 ≤ K ≤ N ≤ 100 2 \leq K \leq N \leq 100 2≤K≤N≤100。
对于 40 % 40 \% 40% 的数据， 2 ≤ K ≤ N ≤ 1 0 4 2 \leq K \leq N \leq 10^{4} 2≤K≤N≤104。
对于 100 % 100 \% 100% 的数据， 2 ≤ K ≤ N ≤ 1 0 5 2 \leq K \leq N \leq 10^{5} 2≤K≤N≤105， 1 ≤ u , v , A i ≤ N 1 \leq u,v,A_{i} \leq N 1≤u,v,Ai≤N， 1 ≤ t ≤ 1 0 5 1 \leq t \leq 10^{5} 1≤t≤105。保证 A i A_{i} Ai 两两不同。
蓝桥杯 2023 省赛 B 组 I 题。
P9245 [蓝桥杯 2023 省 B] 景区导游 LCA 树上倍增
w1[i] 记录i到其父节点的边权。w[i]记录节点i到根节点的边权之和。w[根节点]=0。
性质一：a和b的最近公共祖先是ab。则a和b的最短路是：w[a]+w[b]-w[ab]。
第一步：以任意节点为根（我习惯0），BFS求各节点层次，根节点层次为0。
第二步：层次从小到大枚举节点cur，child是cur的孩子。则w[child] = w[cur]+边权。w1[child]=边权。
第三步：求初始边权之和S。
第四步：
a,0i 。S - (A[0]到A[1]边权)。
b,N-1i。S- （A[N-2]和A[N-1]边权）
c,S - (A[i-1]和A[i]边权) - (A[i+1]和A[i]边权)+(A[i-1]和A[i+1]边权)
代码
核心代码
#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>
#include <bitset>
using namespace std;
template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
in >> pr.first >> pr.second;
return in;
}
template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t);
return in;
}
template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
return in;
}
template<class T = int>
vector<T> Read() {
int n;
cin >> n;
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
vector<T> ret;
T tmp;
while (cin >> tmp) {
ret.emplace_back(tmp);
if ('\n' == cin.get()) { break; }
}
return ret;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<int N = 1'000'000>
class COutBuff
{
public:
COutBuff() {
m_p = puffer;
}
template<class T>
void write(T x) {
int num[28], sp = 0;
if (x < 0)
*m_p++ = '-', x = -x;
if (!x)
*m_p++ = 48;
while (x)
num[++sp] = x % 10, x /= 10;
while (sp)
*m_p++ = num[sp--] + 48;
AuotToFile();
}
void writestr(const char* sz) {
strcpy(m_p, sz);
m_p += strlen(sz);
AuotToFile();
}
inline void write(char ch)
{
*m_p++ = ch;
AuotToFile();
}
inline void ToFile() {
fwrite(puffer, 1, m_p - puffer, stdout);
m_p = puffer;
}
~COutBuff() {
ToFile();
}
private:
inline void AuotToFile() {
if (m_p - puffer > N - 100) {
ToFile();
}
}
char puffer[N], * m_p;
};
template<int N = 1'000'000>
class CInBuff
{
public:
inline CInBuff() {}
inline CInBuff<N>& operator>>(char& ch) {
FileToBuf();
while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车
ch = *S++;
return *this;
}
inline CInBuff<N>& operator>>(int& val) {
FileToBuf();
int x(0), f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
inline CInBuff& operator>>(long long& val) {
FileToBuf();
long long x(0); int f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
template<class T1, class T2>
inline CInBuff& operator>>(pair<T1, T2>& val) {
*this >> val.first >> val.second;
return *this;
}
template<class T1, class T2, class T3>
inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
return *this;
}
template<class T1, class T2, class T3, class T4>
inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
return *this;
}
template<class T = int>
inline CInBuff& operator>>(vector<T>& val) {
int n;
*this >> n;
val.resize(n);
for (int i = 0; i < n; i++) {
*this >> val[i];
}
return *this;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
*this >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> Read() {
vector<T> ret;
*this >> ret;
return ret;
}
private:
inline void FileToBuf() {
const int canRead = m_iWritePos - (S - buffer);
if (canRead >= 100) { return; }
if (m_bFinish) { return; }
for (int i = 0; i < canRead; i++)
{
buffer[i] = S[i];//memcpy出错
}
m_iWritePos = canRead;
buffer[m_iWritePos] = 0;
S = buffer;
int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
if (readCnt <= 0) { m_bFinish = true; return; }
m_iWritePos += readCnt;
buffer[m_iWritePos] = 0;
S = buffer;
}
int m_iWritePos = 0; bool m_bFinish = false;
char buffer[N + 10], * S = buffer;
};
class CBFSLeve {
public:
static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
vector<int> leves(neiBo.size(), -1);
for (const auto& s : start) {
leves[s] = 0;
}
for (int i = 0; i < start.size(); i++) {
for (const auto& next : neiBo[start[i]]) {
if (-1 != leves[next]) { continue; }
leves[next] = leves[start[i]] + 1;
start.emplace_back(next);
}
}
return leves;
}
template<class NextFun>
static vector<int> Leve(int N, NextFun nextFun, vector<int> start) {
vector<int> leves(N, -1);
for (const auto& s : start) {
leves[s] = 0;
}
for (int i = 0; i < start.size(); i++) {
auto nexts = nextFun(start[i]);
for (const auto& next : nexts) {
if (-1 != leves[next]) { continue; }
leves[next] = leves[start[i]] + 1;
start.emplace_back(next);
}
}
return leves;
}
static vector<vector<int>> LeveNodes(const vector<int>& leves) {
const int iMaxLeve = *max_element(leves.begin(), leves.end());
vector<vector<int>> ret(iMaxLeve + 1);
for (int i = 0; i < leves.size(); i++) {
ret[leves[i]].emplace_back(i);
}
return ret;
};
static vector<int> LeveSort(const vector<int>& leves) {
const int iMaxLeve = *max_element(leves.begin(), leves.end());
vector<vector<int>> leveNodes(iMaxLeve + 1);
for (int i = 0; i < leves.size(); i++) {
leveNodes[leves[i]].emplace_back(i);
}
vector<int> ret;
for (const auto& v : leveNodes) {
ret.insert(ret.end(), v.begin(), v.end());
}
return ret;
};
};
class CParents
{
public:
CParents(vector<int>& vParent, long long iMaxDepth)
{
int iBitNum = 0;
for (; iMaxDepth; iBitNum++) {
const auto mask = 1LL << iBitNum;
if (mask & iMaxDepth) { iMaxDepth = iMaxDepth ^ mask; }
}
const int n = vParent.size();
m_vParents.assign(iBitNum + 1, vector<int>(n, -1));
m_vParents[0] = vParent;
//树上倍增
for (int i = 1; i < m_vParents.size(); i++)
{
for (int j = 0; j < n; j++)
{
const int iPre = m_vParents[i - 1][j];
if (-1 != iPre)
{
m_vParents[i][j] = m_vParents[i - 1][iPre];
}
}
}
}
int GetParent(int iNode, int iDepth)const
{
int iParent = iNode;
for (int iBit = 0; iBit < m_vParents.size(); iBit++)
{
if (-1 == iParent)
{
return iParent;
}
if (iDepth & (1 << iBit))
{
iParent = m_vParents[iBit][iParent];
}
}
return iParent;
}
inline int GetBitCnt()const { return m_vParents.size(); };
inline const int& GetPow2Parent(int iNode, int n)const {
return m_vParents[n][iNode];
}
//在leftNodeExclude的1到rightLeve级祖先中查找符合pr的最近祖先
template<class _Pr>
int FindFirst(int leftNodeExclude, int rightLeve, _Pr pr) {
for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
const int iMask = 1 << iBit;
if (!(iMask & rightLeve)) { continue; }
if (pr(m_vParents[iBit][leftNodeExclude])) {
return BFindFirst(leftNodeExclude, iBit, pr);
}
leftNodeExclude = m_vParents[iBit][leftNodeExclude];
}
return -1;
}
//在node的0到rightLeve级祖先中查找符合pr的最远祖先比node高多少层次,这些层次必须存在
template<class _Pr>
int FindEnd(int node, int rightLeve, _Pr pr) {
int leve = 0;
for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
const int iMask = 1 << iBit;
if (!(iMask & rightLeve)) { continue; }
if (!pr(m_vParents[iBit][node])) {
return leve + BFindEnd(node, iBit, pr);
}
node = m_vParents[iBit][node];
leve = leve ^ iMask;
}
return leve;
}
protected:
//在leftNodeExclude的1到2^pow^级祖先中查找符合pr的最近祖先
template<class _Pr>
int BFindFirst(int leftNodeExclude, int pow, _Pr pr) {
while (pow > 0) {
const int& mid = m_vParents[pow - 1][leftNodeExclude];
if (pr(mid)) {
}
else {
leftNodeExclude = mid;
}
pow--;
}
return m_vParents[0][leftNodeExclude];
}
//在node的[0,2^pow^-1]级祖先中寻找符合的最后一个
template<class _Pr>
int BFindEnd(int node, int pow, _Pr pr) {
int leve = 0;
while (pow > 0) {
pow--;
const int& mid = m_vParents[pow][node];
if (pr(mid)) {
node = mid;
leve = leve ^ (1 << pow);
}
else {
}
}
return leve;
}
vector<vector<int>> m_vParents;
};
class C2Parents : public CParents
{
public:
C2Parents(vector<int>& vParent, const vector<int>& vDepth) :m_vDepth(vDepth)
, CParents(vParent, *std::max_element(vDepth.begin(), vDepth.end()))
{
}
int GetPublicParent(int iNode1, int iNode2)const
{
int leve0 = m_vDepth[iNode1];
int leve1 = m_vDepth[iNode2];
if (leve0 < leve1)
{
iNode2 = GetParent(iNode2, leve1 - leve0);
leve1 = leve0;
}
else
{
iNode1 = GetParent(iNode1, leve0 - leve1);
leve0 = leve1;
}
if (iNode1 == iNode2) { return iNode1; }
for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
const int iMask = 1 << iBit;
if (iMask & leve0) {
const int i1 = GetPow2Parent(iNode1, iBit);
const int i2 = GetPow2Parent(iNode2, iBit);
if (i1 == i2) {
while (iBit > 0) {
const int i3 = GetPow2Parent(iNode1, iBit - 1);
const int i4 = GetPow2Parent(iNode2, iBit - 1);
if (i3 != i4) {
iNode1 = i3; iNode2 = i4;
}
iBit--;
}
return GetPow2Parent(iNode1, 0);
}
else {
iNode1 = i1; iNode2 = i2; leve0 -= iMask;
}
}
}
return iNode1;
}
protected:
vector<vector<int>> m_vParents;
const vector<int> m_vDepth;
};
class Solution {
public:
vector<long long> Ans(const int N, vector<tuple<int, int, int>>& edge, vector<int>& A) {
const int K = A.size();
vector<vector<int>> neiBo(N);
for (auto& [u, v, t] : edge) {
u--, v--;
neiBo[u].emplace_back(v);
neiBo[v].emplace_back(u);
}
for (auto& i : A) { i--; }
auto leves = CBFSLeve::Leve(neiBo, { 0 });
auto leveNodes = CBFSLeve::LeveNodes(leves);
vector<int> par(N, -1), w1(N);
vector<long long> w(N);
for (auto& [u, v, t] : edge) {
if (leves[u] > leves[v]) {
swap(u, v);
}
par[v] = u;
w1[v] = t;
}
for (const auto& v : leveNodes) {
for (const auto& cur : v) {
if (-1 == par[cur]) { continue; }
w[cur] = w[par[cur]] + w1[cur];
}
}
C2Parents pars(par, leves);
auto Dis = [&](int a, int b) {
const auto ab = pars.GetPublicParent(a, b);
return w[a] + w[b] - 2 * w[ab];
};
long long S = 0;
for (int i = 1; i < A.size(); i++) {
S += Dis(A[i], A[i - 1]);
}
vector<long long> ans;
ans.emplace_back(S - Dis(A[0], A[1]));
for (int i = 1; i+1 < A.size(); i++) {
long long tmp = Dis(A[i - 1], A[i + 1]) - Dis(A[i - 1], A[i]) - Dis(A[i], A[i + 1]);
ans.emplace_back(S + tmp);
}
ans.emplace_back(S - Dis(A[K - 1], A[K - 2]));
return ans;
}
};
int main() {
#ifdef _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
//ios::sync_with_stdio(0); cin.tie(nullptr);
CInBuff<> in; COutBuff<10'000'000> ob;
int N, K;
in >> N >> K;
auto edge = in.Read <tuple<int,int,int> > (N-1);
auto A = in.Read<int>(K);
#ifdef _DEBUG
printf("N=%d", N);
Out(edge, ",edge=");
Out(A, ",A=");
//Out(B, "B=");
//Out(que, "que=");
//Out(B, "B=");
#endif // DEBUG
auto res = Solution().Ans(N,edge,A);
for (const auto& i : res)
{
cout << i << " ";
}
return 0;
}
单元测试
int N;
vector<tuple<int, int, int>> edge;
vector<int>A;
TEST_METHOD(TestMethod01)
{
N = 6, edge = { {1,2,1},{1,3,1},{3,4,2},{3,5,2},{4,6,3} }, A = { 2,6,5,1 };
auto res = Solution().Ans(N, edge, A);
AssertV({ 10,7,13,14 }, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。