暴力dfs: ``` #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; typedef pair<int,int> pii; map<pii,int>st; int a[N]; vector<pii> edge[N]; //s路径起点 //u当前点 //father父亲节点 //v终点 //sum总和 bool dfs(int s,int u,int father,int v,int sum) { if(u==v) { st[{s,v}]=sum; st[{v,s}]=sum; return true; } for(int i=0;i<edge[u].size();i++) { int son=edge[u][i].first; if(son==father) continue; int w=edge[u][i].second; if(dfs(s,son,u,v,sum+w)) return true; } return false; } signed main() { int n,k; cin>>n>>k; for(int i=0;i<n-1;i++) { int x,y,t; cin>>x>>y>>t; edge[x].push_back({y,t}); edge[y].push_back({x,t}); } for(int i=0;i<k;i++) { cin>>a[i]; } int ans=0; for(int i=0;i<k-1;i++) { dfs(a[i],a[i],-1,a[i+1],0); ans+=st[{a[i],a[i+1]}]; } for(int i=0;i<k;i++) { int tmp=ans; if(i==0) tmp=tmp-(st[{a[i],a[i+1]}]); else if(i==k-1) tmp=tmp-(st[{a[i-1],a[i]}]); else { tmp=tmp-(st[{a[i],a[i+1]}]); tmp=tmp-(st[{a[i-1],a[i]}]); dfs(a[i-1],a[i-1],-1,a[i+1],0); tmp=tmp+(st[{a[i-1],a[i+1]}]); } cout<<tmp<<" "; } return 0; } ``` 正解LCA： ``` #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; typedef pair<int,int> pii; // vector<int> e[N];//存树 int dep[N],fa[N][20]; int n,k; int a[N],sum[N]; vector<pii> edge[N];//存树 void dfs(int u,int father) { dep[u]=dep[father]+1; fa[u][0]=father; for(int i=1;i<=19;i++) { fa[u][i]=fa[fa[u][i-1]][i-1]; } for(auto e:edge[u]) { if(e.first!=father) dfs(e.first,u); } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=19;i>=0;i--) { if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; } if(u==v) return v; for(int i=19;i>=0;i--) { if(fa[u][i]!=fa[v][i]) { u=fa[u][i],v=fa[v][i]; } } return fa[u][0]; } void cal_sum(int u) { for(int i=0;i<edge[u].size();i++) { int s=edge[u][i].first; if(s==fa[u][0]) continue; int w=edge[u][i].second; sum[s]=sum[u]+w; cal_sum(s); } } signed main() { cin>>n>>k; for(int i=0;i<n-1;i++) { int x,y,t; cin>>x>>y>>t; edge[x].push_back({y,t}); edge[y].push_back({x,t}); } for(int i=1;i<=k;i++) { cin>>a[i]; } dfs(1,0); cal_sum(1); int ans=0; for(int i=1;i<=k-1;i++) { int u=a[i],v=a[i+1]; int cost=sum[u]+sum[v]-2*sum[lca(u,v)]; ans+=cost; } for(int i=1;i<=k;i++) { int tmp=ans; if(i==1) { tmp=tmp-(sum[a[i+1]]+sum[a[i]]-sum[lca(a[i],a[i+1])]*2); } else if(i==k) { tmp=tmp-(sum[a[i-1]]+sum[a[i]]-sum[lca(a[i],a[i-1])]*2); } else { tmp=tmp-(sum[a[i-1]]+sum[a[i]]-sum[lca(a[i],a[i-1])]*2); tmp=tmp-(sum[a[i+1]]+sum[a[i]]-sum[lca(a[i],a[i+1])]*2); tmp=tmp+(sum[a[i-1]]+sum[a[i+1]]-sum[lca(a[i+1],a[i-1])]*2); } cout<<tmp<<" "; } return 0; } ```

树上倍增 (最近公共祖先问题 pa[][]的推导可以尝试这题: 1483. 树节点的第 K 个祖先 - 力扣（LeetCode） (再不济可以看看【模板讲解】树上倍增算法（以及最近公共祖先）Python/Java/C++/Go)) 然后就是把 单纯的 (祖先) 拓展为 (祖先, 本节点到祖先的距离)即可 不知道为什么这里提交不过, 我在蓝桥杯2023年第十四届省赛真题-景区导游 - C语言网 (dotcpp.com)提交是没问题的!😄 ```cpp #include <cstdio> #include <vector> #include <tuple> #include <queue> #include <utility> #include <functional> using namespace std; using ll = long long; // 获取二进制位数 int getBit(int x) { int res = 0; while (x) { ++res; x >>= 1; } return res; } int main() { int n, k; scanf("%d %d", &n, &k); int nBit = getBit(n); vector<vector<pair<int, int>>> pa(n, vector<pair<int, int>>(nBit, make_pair(-1, -1))); vector<int> hArr(n, 0); // 深度 vector<vector<pair<int, int>>> G(n); // [u][v, w] for (int i = 1; i < n; ++i) { int u, v, w; scanf("%d %d %d", &u, &v, &w); --u, --v; // 映射到索引 G[u].push_back(make_pair(v, w)); G[v].push_back(make_pair(u, w)); } // 预处理 function<void(int, int, int)> dfs = [&](int i, int p, int pw) { pa[i][0] = make_pair(p, pw); for (auto& it : G[i]) { int v, w; tie(v, w) = it; if (v != p) { hArr[v] = hArr[i] + 1; dfs(v, i, w); } } }; // tmd 根是tm的誰?! (先假设是0) (好像是誰无所谓?) dfs(0, -1, -1); // dp 计算所有节点的2^b个祖先结点 以及到达他们的权 for (int b = 1; b < nBit; ++b) { for (int i = 0; i < n; ++i) { int v1, v2, w1, w2; tie(v1, w1) = pa[i][b - 1]; if (v1 != -1) { tie(v2, w2) = pa[v1][b - 1]; pa[i][b] = make_pair(v2, w1 + w2); } } } function<ll(int, int)> lac = [&](int a, int b) { if (hArr[a] < hArr[b]) { // 保证 a 是根深的结点 int tmp = a; a = b; b = tmp; } ll res = 0; int h = hArr[a] - hArr[b], bitH = 0; // 现在 把 a 向上移动 hArr[a] - hArr[b] 个距离, 保证 ab 处于同一层 while (h) { if (h & 1) { int new_a, new_w; tie(new_a, new_w) = pa[a][bitH]; if (new_a == -1) break; res += new_w; a = new_a; } ++bitH; h >>= 1; } if (a == b) { // a 的最近祖先是 b ! return res; } // 二分跳 for (int t = pa[a].size() - 1; t >= 0; --t) { int av, aw, bv, bw; tie(av, aw) = pa[a][t]; tie(bv, bw) = pa[b][t]; if (av != bv) { a = av; b = bv; res += (aw + bw); } } int av, aw, bv, bw; tie(av, aw) = pa[a][0]; tie(bv, bw) = pa[b][0]; return res + aw + bw; }; // 我进行询问 ll sum = 0; // 总距离 vector<int> arr(k); for (int i = 0; i < k; ++i) { scanf("%d", &arr[i]); --arr[i]; if (i > 0) sum += lac(arr[i - 1], arr[i]); } for (int i = 0; i < k; ++i) { if (i == 0) { printf("%lld ", sum - lac(arr[0], arr[1])); } else if (i == k - 1) { printf("%lld ", sum - lac(arr[i - 1], arr[i])); } else { // a -> b -> c -> d // a -> c -> d (减去了-> b ->, 加上了 a->c) printf("%lld ", sum - lac(arr[i - 1], arr[i]) - lac(arr[i], arr[i + 1]) + lac(arr[i - 1], arr[i + 1]) ); } } return 0; } ```

``` #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10, M = 2 * N; int h[N], e[M], ne[M], w[M] , idx; int depth[N], fa[N][21]; int aa[N], dist[N]; int n, m; void add(int a, int b, int c) { e[++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx; } void bfs() { memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[1] = 1; queue<int> q; q.push(1); while(q.size()){ int t = q.front(); q.pop(); for(int i = h[t]; i; i = ne[i]) { int j = e[i]; if(depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; dist[j] = dist[t] + w[i]; q.push(j); fa[j][0] = t; for(int k = 1; (1 << k) <= depth[j]; k ++ ) fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } } int lca(int a, int b) { // 当a在b上面是交换a，b if(depth[a] < depth[b]) swap(a, b); // 把a跳上来，直到a与b同层 for(int k = 20; k >= 0; k -- ) if(depth[fa[a][k]] >= depth[b]) // 从跳大层往跳小层试，一直到a，b同层 a = fa[a][k]; // 当在不断接近b时，让a到接近后的节点上，再去跳更小层 // 为了实现跳奇数层，即a肯定能跳到b同层或b下一层，取k = 0 后会跳到与b同层 if(a == b) return a; // 如果相等，那b就是a和b的公共祖先 for(int k = 20; k >= 0; k -- ) if(fa[a][k] != fa[b][k]) // 记录a，b 最后不是同一个节点的各自的节点 { a = fa[a][k]; b = fa[b][k]; } return fa[a][0]; // 看a，b再跳一层后的结果 } int get_dist(int a, int b) { return dist[aa[a]] + dist[aa[b]] - 2 * dist[lca(aa[a], aa[b])]; } signed main() { cin >> n >> m; memset(h, -1, sizeof h); for(int i = 1; i <= n - 1; i ++ ){ int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } bfs(); int sum = 0; for(int i = 1; i <= m; i ++ ) { cin >> aa[i]; if(i > 1) sum += get_dist(i, i - 1); } for(int i = 1; i <= m; i ++ ) { if(i == 1) cout << sum - get_dist(i, i + 1) << " "; else if(i == m) cout << sum - get_dist(i - 1, i) << endl; else cout << sum - get_dist(i - 1, i) - get_dist(i, i + 1) + get_dist(i - 1, i + 1) << " "; } return 0; } ```