开车

小S在的城镇是一棵树，有\(n?1\)条道路连接了\(n\)个节点，经过每条路需要花一定时间。

现在，小S车上有\(K\)个乘客，第\(i\)个想去的地方是\(a_i\)。（保证\(a_i\)互不相同）

现在，小S想要知道，如果他从每个点出发，载着这\(K\)个人，把他们送到他们各自想到的地方，所需的最少时间是多少。（注意，小S不必再回到起点）。

输入格式
第一行两个整数\(n,K\)。

接下来\(n?1\)行，每行一个整数\(x,y,w\)，分别表示道路连接的节点和经过所需的时间。节点标号从1开始。

接下来\(K\)行，每行一个整数表示\(a_i\)。

输出格式
输出i行，第i行表示小S从\(i\)号节点出发的答案。

样例1
input

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

output

5
3
7
2
2

样例2
input

7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7

output

11
15
10
13
16
15
10

数据范围
对于50%的数据,\(1≤N≤2000\)
对于100%的数据,\(1≤N≤5×10^5,1≤K≤N\)，边的权值\(≤10^6\)。

时间限制：1S

空间限制：256MB

如果给题目加一个条件：送完所有人还要回到根节点，那要怎么做呢？其实答案就是将根节点和所有人要到的点连起来的总边权和乘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