AcWing 4962. 景区导游
原题链接
困难
作者:
FZheng
,
2024-04-08 19:44:56
,
所有人可见
,
阅读 5
LCA
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct EDGE{int v;int t;};
const int N = 1e5+2;
vector<EDGE> tr[N];
int dep[N],dist[N];
int fa[N][18];
void dfs(int u){
for(auto [v,t]:tr[u]){
if(dep[v]) continue;
dep[v] = dep[u] + 1;
dist[v] = dist[u] + t;
fa[v][0] = u;
for(int j=1;j<=17;j++){
fa[v][j] = fa[fa[v][j-1]][j-1];
}
dfs(v);
}
}
int lca(int a,int b){
if(dep[a] < dep[b]) swap(a,b);
for(int k=17;k>=0;k--){
if(dep[fa[a][k]] >= dep[b]) a = fa[a][k];
}
if(a == b) return a;
for(int k=17;k>=0;k--){
if(fa[a][k] != fa[b][k]){ //当k过大时,俩全跳到0,故不会跳了
a = fa[a][k],b = fa[b][k];
}
}
return fa[a][0]; //注意,是跳到lca的亲儿子,不是直接跳到lca
}
int disssssss(int a,int b){
return dist[a] + dist[b] - 2 * dist[lca(a,b)];
}
signed main(){
int n,k;
cin>>n>>k;
for(int i=1;i<n;i++){
int u,v,t;
cin>>u>>v>>t;
tr[u].push_back({v,t});
tr[v].push_back({u,t});
}
dep[1] = 1;
dist[1] = 0;
dfs(1);
vector<int> a(k+1);
for(int i=1;i<=n;i++) cin>>a[i];
int all = 0;
for(int i=2;i<=k;i++){
all += disssssss(a[i-1],a[i]);
}
vector<int> ans(k+1);
ans[1] = all - disssssss(a[1],a[2]);
for(int i=2;i<k;i++){
int d = disssssss(a[i-1],a[i]) + disssssss(a[i],a[i+1]) - (disssssss(a[i-1],a[i+1]));
ans[i] = all - d;
}
ans[k] = all - disssssss(a[k],a[k-1]);
for(int i=1;i<=k;i++) cout<<ans[i]<<' ';
return 0;
}