Description

一颗树n个点，n-1条边，经过每条边都要花费一定的时间，任意两个点都是联通的。

有K个人（分布在K个不同的点）要集中到一个点举行聚会。

聚会结束后需要一辆车从举行聚会的这点出发，把这K个人分别送回去。

请你回答，对于i=1~n，如果在第i个点举行聚会，司机最少需要多少时间把K个人都送回家。

Input

第一行两个数，n，K。

接下来n-1行，每行三个数，x，y，z表示x到y之间有一条需要花费z时间的边。

接下来K行，每行一个数，表示K个人的分布。

Output

输出n个数，第i行的数表示：如果在第i个点举行聚会，司机需要的最少时间。

Sample Input

7 2

1 2 4

1 3 1

2 5 1

2 4 2

4 7 3

4 6 2

3

7

Sample Output

11

15

10

13

16

15

10

HINT

【数据规模】

K <= N <= 500000

1 <= x,y <= N, 1 <= z <= 1000000

Solution

总体上是用全部的路程减去最大的一条路程

先两次dfs求出每个点全部路程

再两次dfs求出最大一条路径

Code

//By Menteur_Hxy#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define M(a,b) memset(a,(b),sizeof(a))#define F(i,a,b) for(register int i=(a);i<=(b);i++)#define E(i,u) for(register int i=head[u];i;i=nxt[i])using namespace std;typedef long long LL;int read() {    int x=0,f=1; char c=getchar();    while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();    return x*f;}const int N=500010;const LL INF=0x7fffffffffffffff;int n,k,cnt;int nxt[N<<1],to[N<<1],w[N<<1],head[N],siz[N];LL dis[N],down[N][2],up[N];void dfs1(int u,int pre) { //向下     E(i,u) { int v=to[i];        if(v==pre) continue;        dfs1(v,u); siz[u]+=siz[v];        dis[u]+=dis[v]+(siz[v]?w[i]:0);    }}void dfs2(int u,int pre) { //向上     E(i,u) { int v=to[i];        if(v==pre) continue;        dis[v]=dis[u];//      if(siz[v])dis[v]-=w[i];//        if(siz[v]
         
          down[u][0]) down[u][1]=down[u][0],down[u][0]=down[v][0]+w[i]; else if(down[v][0]+w[i]>down[u][1]) down[u][1]=down[v][0]+w[i]; }}void dfs4(int u,int pre) { //向上 E(i,u) { int v=to[i]; if(v==pre) continue; if(down[v][0]+w[i]==down[u][0]) up[v]=down[u][1]+w[i]; else up[v]=down[u][0]+w[i]; up[v]=max(up[v],up[u]+w[i]); dfs4(v,u); }}#define add(a,b,c) nxt[++cnt]=head[a],to[cnt]=b,w[cnt]=c,head[a]=cntint main() { n=read(),k=read(); F(i,1,n-1) { int a=read(),b=read(),c=read(); add(a,b,c),add(b,a,c); } F(i,1,k) siz[read()]=1; dfs1(1,0); dfs2(1,0); dfs3(1,0); up[1]=(siz[1]?0:-INF); dfs4(1,0);// F(i,1,n) printf("%lld ",2*dis[i]);cout<