蓝桥杯2023年第十四届省赛真题-景区导游 LCA+前缀和

解题思路: 

定义 tp[i] 代表点 i 距离根节点的边权之和

题目要求输出的是跳过点 i 后乘车的时间，所以可以提前求出乘车的总时间，在便利到点 i 时减去从 i−1 到 i 和从 i 到 i+1 的时间，然后加上从 i−1 到 i+1 的时间。别忘了特判当 i 等于 1 和 k 的情况。
注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define N 200005
struct node{
	ll x,y;
};
vector<node> e[N];
ll n,k; 
ll fa[N],son[N],sz[N],dep[N],top[N];
ll tp[N];
ll kk[N];
void dfs1(ll u,ll f){
	fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
	for(node v:e[u]){
		if(v.x==f)continue;
		dfs1(v.x,u);
		sz[u]+=sz[v.x];
		if(sz[son[u]]<sz[v.x])son[u]=v.x;
	}
} 
void dfs2(ll u,ll t){
	top[u]=t;
	if(!son[u])return;
	dfs2(son[u],t);
	for(node v:e[u]){
		if(v.x==fa[u]||v.x==son[u])continue;
		dfs2(v.x,v.x);
	}
}
ll lca(ll u,ll v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v; 
}
void dfs(ll u){
	for(node v:e[u]){
		if(v.x==fa[u])continue;
		tp[v.x]=tp[u]+v.y;
		dfs(v.x); 
	}
}
int main(){
	cin>>n>>k;
	for(ll i=1;i<n;i++){
		ll u,v,t;cin>>u>>v>>t;  
		e[u].push_back({v,t});
		e[v].push_back({u,t});
	}
	dfs1(1,0),dfs2(1,1);
	dfs(1); 
	//for(ll i=1;i<=n;i++)cout<<tp[i]<<endl;
	for(ll i=1;i<=k;i++)cin>>kk[i];
	ll sum=0;
	for(ll i=1;i<k;i++){
		sum+=tp[kk[i]]+tp[kk[i+1]]-2*tp[lca(kk[i],kk[i+1])];
	}
	for(ll i=1;i<=k;i++){
		ll ans=sum;
		if(i==1){
			ans-=tp[kk[i]]+tp[kk[i+1]]-2*tp[lca(kk[i],kk[i+1])];
			cout<<ans<<' ';
		}
		else if(i>1&&i<k){
			ans-=tp[kk[i-1]]+tp[kk[i]]-2*tp[lca(kk[i-1],kk[i])];
			ans-=tp[kk[i]]+tp[kk[i+1]]-2*tp[lca(kk[i],kk[i+1])];
			ans+=tp[kk[i-1]]+tp[kk[i+1]]-2*tp[lca(kk[i-1],kk[i+1])];
			cout<<ans<<' ';
		}
		else{
			ans-=tp[kk[i-1]]+tp[kk[i]]-2*tp[lca(kk[i-1],kk[i])];
			cout<<ans<<' ';
		} 
	}
	return 0;
}