Description：

一棵树上标记 $k$ 个点，问在树上每个点遍历所有标记的点的最短距离。

$n \le 5\times 10^5$

Solution：

首先发现在一个点的距离就是到所有点所经过的边的二倍减去这个点到最远的点的距离，第一部分用二次扫描加换根即可，先把斯坦纳树求出来，方法是找一个标记的点求出所有点到这个点的路径的总长度重复的边只算一遍，然后再 $dp$ 一遍如果在树上走，那么这个点的值就是斯坦纳树，如果不在树上走，就在父亲的基础上加上这条边的值，第二部分也是二次扫描加换根，但是要维护到根的一个最长链，一个次长链，因为在第二次 $dp$ 时如果发现是当前点更新的父亲，就要用次长链来更新这个点的值，因为如果用最长链会走两遍父子边，而且如果用最长链更新了最长链，就不能用次长链更新次长链，也是因为会走两遍，第二次 $dp$ 时也要求出最长链和次长链，因为他的儿子还要用它的次长链更新，更新方式相同。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 500010

typedef long long ll;

#define INF 0x3f3f3f3f3f3f3f3f

struct edge

{

	int to,nxt;

	ll v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

}

int pos[MAXN];

bool key[MAXN];

ll g1[MAXN],g2[MAXN];

bool v[MAXN];

bool tag[MAXN];

void dp1(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp1(e[i].to);

		if(tag[e[i].to])g1[k] += g1[e[i].to] + e[i].v;

	}

	if(g1[k] != 0)tag[k] = true;

	return;

}

int st;

void dp2(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		if(!tag[e[i].to])g2[e[i].to] = g2[k] + e[i].v;

		else g2[e[i].to] = g1[st];

		dp2(e[i].to);

	}

	return;

}

ll f1[MAXN],f2[MAXN];

void dp3(int k)

{

	v[k] = true;

	if(key[k]){f1[k] = 0;f2[k] = -INF;}

	else{f1[k] = f2[k] = -INF;}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp3(e[i].to);

		if(f1[e[i].to] + e[i].v >= f1[k])

		{

			f2[k] = f1[k];

			f1[k] = f1[e[i].to] + e[i].v;

		}

		else if(f1[e[i].to] + e[i].v > f2[k])

			f2[k] = f1[e[i].to] + e[i].v;

	}

	return;

}

void dp4(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		int tmp;

		if(f1[e[i].to] + e[i].v == f1[k])tmp = f2[k] + e[i].v;

		else tmp = f1[k] + e[i].v;

		if(tmp >= f1[e[i].to]){f2[e[i].to] = f1[e[i].to];f1[e[i].to] = tmp;}

		else if(tmp > f2[e[i].to])f2[e[i].to] = tmp;

		dp4(e[i].to);

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&k);

	int a,b;

	ll c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%lld",&a,&b,&c);

		add(a,b,c);

	}

	for(int i = 1;i <= k;++i)

	{

		scanf("%d",&pos[i]);

		key[pos[i]] = true;tag[pos[i]] = true;

		st = pos[i];

	}

	memset(v,false,sizeof(v));dp1(st);

	g2[st] = g1[st];

	memset(v,false,sizeof(v));dp2(st);

	memset(v,false,sizeof(v));dp3(st);

	memset(v,false,sizeof(v));dp4(st);

	for(int i = 1;i <= n;++i)

	{

		printf("%lld\n",g2[i] * 2 - f1[i]);

	}

	return 0;

}