3156: 蓝桥杯2023年第十四届省赛真题-景区导游

解题思路:利用公式dis[a]-dis[b]-2*dis[lca(a,b)]求出a与b之间的距离，dis为此节点到根节点的距离

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int to;
	int next;
	long long w;
}mp[1000005];
int head[100005];
long long dis[100005];
int a[100005];
long long sum[100005];
int cnt=0;
void add(int a,int b,int c)
{
	mp[++cnt].to=b;
	mp[cnt].next=head[a];
	mp[cnt].w=c;
	head[a]=cnt;
}
int st[500005][25];
int deep[500055];
void dfs(int u,int fa,long long w)
{
	deep[u]=deep[fa]+1;
	st[u][0]=fa;
	for(int i=1;i<=19;i++)
	{
		st[u][i]=st[st[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=mp[i].next)
	{
		int v=mp[i].to;
		if(v!=fa)
		{
			dfs(v,u,w+mp[i].w);
		}	
	}
	dis[u]=w;
}
int lca(int a,int b)
{
	if(deep[a]<deep[b])swap(a,b);
	for(int i=19;i>=0;i--)
	{
		if(deep[st[a][i]]>=deep[b])
		{
			a=st[a][i];
		}
	}
	if(a==b)return a;
	for(int i=19;i>=0;i--)
	{
		if(st[a][i]!=st[b][i])
		{
			a=st[a][i];
			b=st[b][i];
		}
	}
	return st[a][0];
}
int main()
{
	int n,m,s;
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	dfs(1,0,0);
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
	}
	long long ans=0;
	for(int i=2;i<=m;i++)
	{
		sum[i-1]=dis[a[i-1]]+dis[a[i]]-2*dis[lca(a[i-1],a[i])];
		ans+=sum[i-1];
	}
	for(int i=1;i<=m;i++)
	{
		if(i==m)
		{
			cout<<ans-sum[i-1]<<' ';
		}
		else if(i==1)
		{
			cout<<ans-sum[i]<<' ';
		}
		else
		{
			long long add;
			add=dis[a[i-1]]+dis[a[i+1]]-2*dis[lca(a[i-1],a[i+1])];
			cout<<ans+add-sum[i]-sum[i-1]<<' ';
		}
	}
	return 0;
}