第十四届蓝桥杯省赛C/C++ 大学 B 组 景区导游

本题是一道LCA最近公共祖先的题目我刚开始用floyd暴力求解只过了20%的数据。上代码#includeiostream #includevector using namespace std; #define int long long const int N 1e5 10; int deep[N]; int d[N]; int fa[N][25]; int lj[N]; int dep[N]; vectorpairint, int g[N];//编号长度 void dfs(int root, int father) { deep[root] deep[father] 1; fa[root][0] father; for (int i 1; i 20; i) { fa[root][i] fa[fa[root][i - 1]][i - 1]; } for (auto i : g[root]) { if (i.first father) continue; dep[i.first] dep[root] i.second;// dfs(i.first, root); } } int lca(int index, int index1) { if (deep[index] deep[index1])// { swap(index, index1); } for (int i 20; i 0; i--) { if (deep[fa[index][i]] deep[index1])// index fa[index][i]; } if (index index1) return index; for (int i 20; i 0; i--) { if (fa[index][i] ! fa[index1][i])// { index fa[index][i]; index1 fa[index1][i]; } } return fa[index][0];// } int f2(int index, int index1) { if (index 0 || index1 0) return 0; return dep[index] dep[index1] - 2 * dep[lca(index, index1)]; } signed main() { int n, m; cin n m; for (int i 1; i n; i) { int u, v, w; cin u v w; g[u].push_back({ v,w }); g[v].push_back({ u,w }); } dfs(1, 0); int sum 0; for (int i 1; i m; i) { cin lj[i]; if (i ! 1) { sum f2(lj[i - 1], lj[i]); } } for (int i 1; i m; i) { cout sum - f2(lj[i - 1], lj[i]) - f2(lj[i 1], lj[i]) f2(lj[i - 1], lj[i 1]) ; } return 0; }需要注意lca内部是先把两节点跳到同一深度再跳到他们的公共祖先这里我写了很久才发现自己写错了。