蓝桥杯2023年第十四届省赛真题-景区导游 LCA+前缀和
摘要：解题思路:定义 tp[i]代表点i距离根节点的边权之和题目要求输出的是跳过点i后乘车的时间，所以可以提前求出乘车的总时间，在便利……
景区导游（LCA详解）
#includeusingnamespacestd;typedeflonglongll;constintN=1e5+5;intfa[N][21],deep[N];vectortree[N],tep[N];llpath[N];intn,
3156: 蓝桥杯2023年第十四届省赛真题-景区导游
摘要：解题思路:利用公式dis[a]-dis[b]-2*dis[lca(a,b)]求出a与b之间的距离，dis为此节点到根节点的距离注意事项:参考代码:#include<bits/stdc++.h>
us……
景区导游（tarjan算法求LCA）
摘要：解题思路:思路详解见：https://www.acwing.com/solution/content/239076/参考代码:#include <iostream>
#include <cstrin……
景区导游详细注释--先暴力->再借助最小公共祖先（树链剖分）优化
解题思路:游览顺序为2651，当跳过中间某个景点时(例如6)要花费的时间为总时间减去该景点与前一个景点的时间（2->6)，再减去该景点与后一个景点的时间（6->5），最后再加上前一个景点的时间到后一个景点的时间（2->5）,跳过第一个或者最后一个时只需要减去后一段或前一段时间；注意事项:参考代码:先看
tarjan算法求lca
#代码```cpp#include#include#include#include#include#include#include#include#include//#include#include#include#definelowbit(x)(-x)&x#definelllonglongconst