word超链接网站怎样做,wordpress图片简码,wordpress 主题 academy,常熟网站建设专业的公司本文涉及知识点
树上倍增
P9245 [蓝桥杯 2023 省 B] 景区导游
题目描述
某景区一共有 NNN 个景点#xff0c;编号 111 到 NNN。景点之间共有 N−1N-1N−1 条双向的摆渡车线路相连#xff0c;形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行#xff0c;需要花费…本文涉及知识点
树上倍增
P9245 [蓝桥杯 2023 省 B] 景区导游
题目描述
某景区一共有 NNN 个景点编号 111 到 NNN。景点之间共有 N−1N-1N−1 条双向的摆渡车线路相连形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行需要花费一定的时间。
小明是这个景区的资深导游他每天都要按固定顺序带客人游览其中 KKK 个景点A1,A2,…,AKA_{1},A_{2},\ldots,A_{K}A1,A2,…,AK。今天由于时间原因小明决定跳过其中一个景点只带游客按顺序游览其中 K−1K-1K−1 个景点。具体来说如果小明选择跳过 AiA_{i}Ai那么他会按顺序带游客游览 A1,A2,…,Ai−1,Ai1,…,AK(1≤i≤K)A_{1},A_{2},\ldots,A_{i-1},A_{i1},\ldots,A_{K}(1 \leq i \leq K)A1,A2,…,Ai−1,Ai1,…,AK(1≤i≤K)。
请你对任意一个 AiA_{i}Ai计算如果跳过这个景点小明需要花费多少时间在景点之间的摆渡车上
输入格式
第一行包含 222 个整数 NNN 和 KKK。
以下 N−1N-1N−1 行每行包含 333 个整数 uv,tuv, tuv,t代表景点 uuu 和 vvv 之间有摆渡车线路花费 ttt 个单位时间。
最后一行包含 KKK 个整数 A1,A2,…,AKA_{1},A_{2},\ldots,A_{K}A1,A2,…,AK 代表原定游览线路。
输出格式
输出 KKK 个整数其中第 iii 个代表跳过 AiA_{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→12 \rightarrow 6 \rightarrow 5 \rightarrow 12→6→5→1。
当跳过 222 时路线是 6→5→16 \rightarrow 5 \rightarrow 16→5→1其中 6→56 \rightarrow 56→5 花费时间 3227322732275→15 \rightarrow 15→1 花费时间 213213213总时间花费 101010。
当跳过 666 时路线是 2→5→12 \rightarrow 5 \rightarrow 12→5→1其中 2→52 \rightarrow 52→5 花费时间 1124112411245→15 \rightarrow 15→1 花费时间 213213213总时间花费 777。
当跳过 555 时路线是 2→6→12 \rightarrow 6 \rightarrow 12→6→1其中 2→62 \rightarrow 62→6 花费时间 1123711237112376→16 \rightarrow 16→1 花费时间 321632163216 总时间花费 131313。
当跳过 111 时路线时 2→6→52 \rightarrow 6 \rightarrow 52→6→5其中 2→62 \rightarrow 62→6 花费时间 1123711237112376→56 \rightarrow 56→5 花费时间 322732273227 总时间花费 141414。
【评测用例规模与约定】
对于 20%20 \%20% 的数据2≤K≤N≤1002 \leq K \leq N \leq 1002≤K≤N≤100。
对于 40%40 \%40% 的数据2≤K≤N≤1042 \leq K \leq N \leq 10^{4}2≤K≤N≤104。
对于 100%100 \%100% 的数据2≤K≤N≤1052 \leq K \leq N \leq 10^{5}2≤K≤N≤1051≤u,v,Ai≤N1 \leq u,v,A_{i} \leq N1≤u,v,Ai≤N1≤t≤1051 \leq t \leq 10^{5}1≤t≤105。保证 AiA_{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]。 第一步以任意节点为根我习惯0BFS求各节点层次根节点层次为0。 第二步层次从小到大枚举节点curchild是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[i1]和A[i]边权)(A[i-1]和A[i1]边权)
代码
核心代码
#include iostream
#include sstream
#include vector
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist
#includearray#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T int
vectorT Read() {int n;cin n;vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}
templateclass T int
vectorT ReadNotNum() {vectorT ret;T tmp;while (cin tmp) {ret.emplace_back(tmp);if (\n cin.get()) { break; }}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid 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;
};templateint N 1000000
class CInBuff
{
public:inline CInBuff() {}inline CInBuffN operator(char ch) {FileToBuf();while ((\r *S) || (\n *S) || ( *S)) { S; }//忽略空格和回车ch *S;return *this;}inline CInBuffN 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;}templateclass T1, class T2inline CInBuff operator(pairT1, T2 val) {*this val.first val.second;return *this;}templateclass T1, class T2, class T3inline CInBuff operator(tupleT1, T2, T3 val) {*this get0(val) get1(val) get2(val);return *this;}templateclass T1, class T2, class T3, class T4inline CInBuff operator(tupleT1, T2, T3, T4 val) {*this get0(val) get1(val) get2(val) get3(val);return *this;}templateclass T intinline CInBuff operator(vectorT val) {int n;*this n;val.resize(n);for (int i 0; i n; i) {*this val[i];}return *this;}templateclass T intvectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {*this ret[i];}return ret;}templateclass T intvectorT Read() {vectorT 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 vectorint Leve(const vectorvectorint neiBo, vectorint start) {vectorint 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;}templateclass NextFunstatic vectorint Leve(int N, NextFun nextFun, vectorint start) {vectorint 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 vectorvectorint LeveNodes(const vectorint leves) {const int iMaxLeve *max_element(leves.begin(), leves.end());vectorvectorint ret(iMaxLeve 1);for (int i 0; i leves.size(); i) {ret[leves[i]].emplace_back(i);}return ret;};static vectorint LeveSort(const vectorint leves) {const int iMaxLeve *max_element(leves.begin(), leves.end());vectorvectorint leveNodes(iMaxLeve 1);for (int i 0; i leves.size(); i) {leveNodes[leves[i]].emplace_back(i);}vectorint ret;for (const auto v : leveNodes) {ret.insert(ret.end(), v.begin(), v.end());}return ret;};
};
class CParents
{
public:CParents(vectorint 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, vectorint(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的最近祖先templateclass _Print 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高多少层次,这些层次必须存在templateclass _Print 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的最近祖先templateclass _Print 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]级祖先中寻找符合的最后一个templateclass _Print 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;}vectorvectorint m_vParents;
};class C2Parents : public CParents
{
public:C2Parents(vectorint vParent, const vectorint 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:vectorvectorint m_vParents;const vectorint m_vDepth;
};class Solution {
public:vectorlong long Ans(const int N, vectortupleint, int, int edge, vectorint A) {const int K A.size();vectorvectorint 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);vectorint par(N, -1), w1(N);vectorlong 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]);}vectorlong long ans;ans.emplace_back(S - Dis(A[0], A[1]));for (int i 1; i1 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 _DEBUGfreopen(a.in, r, stdin);
#endif // DEBUG //ios::sync_with_stdio(0); cin.tie(nullptr);CInBuff in; COutBuff10000000 ob; int N, K;in N K;auto edge in.Read tupleint,int,int (N-1);auto A in.Readint(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;vectortupleint, int, int edge;vectorintA;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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
