Truck

有一棵 \(n\) 个点的树，边有长度（卡车经过所需时间）。有 \(k\) 个人，第 \(i\) 个人要去 \(p_i\) 号点。

有一个卡车司机，他要载着这些人从某个起点出发，他可以按照自己希望的顺序把这些人送到目的地，把 \(k\) 个人送到目的地后就可以停下来了。

求起点是 \(1\cdots n\) 时，卡车司机所需的最小时间。

输入格式
第一行两个整数 n,k 。

接下来的 \(n?1\) 行每行三个整数 \(x_i,y_i,z_i\) 表示一条 \(x_i\) 与 \(y_i\) 之间的长度为 \(z_i\) 的边。

接下来的 \(k\) 行每行一个整数表示 \(p_i\) 。

输出格式
\(n\) 行，第 $i $行表示起点为 \(i\) 时的最小时间。

样例
input

5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5

output

5
3
7
2
2

数据范围
对于 50% 的数据， \(n≤2000\) 。

对于 100% 的数据， \(k≤n≤5×10^5,1≤z_i≤10^6\) 。

如果给题目加一个条件：送完所有人还要回到根节点，那要怎么做呢？其实答案就是将根节点和所有人要到的点连起来的总边权和乘2.我们求出一个根的之后，走一条边，如果这条边属于原来的边集，那么答案不变。否则答案增加走的这条边的两倍。同时如果走了这条边后从\(u\)到达\(v\)，以v为根是\(u\)这颗子树上没有人去，答案减去这条边的两倍。

但是这个条件不存在，所以我们还要减去距离根节点最远的点离根节点的距离。所以我们还要在换根法时还要处理出离这个点最远的点。把点分为子树内的和子树外的，子树内的通过树形dp求出，子树外的要在换根法时求出。那么从u走到v时，首先在不和\(u\)这颗子树的就在换根法中求下来，还有就在\(u\)这颗子树的，定义\(dp_i\)为\(i\)的子树内最远点的距离。。如果\(dp_u=dp_v+1\),那么就要取不严格次大值。否则就取最大值，更新换根法中的子树外最远的点。

#include
#include 
#include
using namespace std;
const int N=5e5+5;
int n,k,x,y,z,hd[N],dp[N],f[N],p,sz[N];
long long ret,ans[N];
struct edge{
	int v,nxt,w;
}e[N<<1];
void add_edge(int x,int y,int w,int z)
{
	e[z]=(edge){y,hd[x],w};
	hd[x]=z;
}
void dfs(int x,int y)
{
	for(int i=hd[x];i;i=e[i].nxt)
	{
		if(e[i].v!=y)
		{
			dfs(e[i].v,x);
			if(sz[e[i].v])
				sz[x]+=sz[e[i].v],ret+=e[i].w<<1;
			p=dp[e[i].v]+e[i].w,z=f[e[i].v]+e[i].w;
			if(p>dp[x]) 
				f[x]=dp[x],dp[x]=p;
			else if(p>f[x])
				f[x]=p;
			else if(z>f[x])
				f[x]=z;
		}     
	}
}
void sou(int x,int y,long long z,int s)
{  
	ans[x]=z-max(s,dp[x]);
	for(int i=hd[x];i;i=e[i].nxt)
	{
		if(e[i].v!=y)
		{
			if(sz[e[i].v]==k)
				p=-1;
			else if(!sz[e[i].v])
				p=1;
			else
				p=0;
			if(dp[e[i].v]+e[i].w==dp[x])
				sou(e[i].v,x,z+p*e[i].w*2,max(f[x],s)+e[i].w);
			else
				sou(e[i].v,x,z+p*e[i].w*2,max(dp[x],s)+e[i].w);
		}
	}
}
int main()
{
	memset(dp,-9,sizeof(dp));
	memset(f,-9,sizeof(f));
	scanf("%d%d",&n,&k);
	for(int i=1;i