思路
可以考虑另一种想法：因为我们发现，答案是肯定不会大于在原来的树上的最短路径的。所以原来的最短路是（有可能的）最大值！
我们把树变成这样，提取出1~n的路径，方便观看撕烤：
（它有个我起的名字，叫灯笼树态,处理树上路径与其余部分之间的关系时画图用，并非真实的数据结构)
我们称被提取出来的树上路径（本题为1~n）为灯笼线，路径上每一个节点及其下悬挂的子树称为灯笼子树，每一个灯笼子树的根节点叫悬挂点。
显然，悬挂点一定在灯笼线上。任意一个点的悬挂点就是它所在的灯笼子树的悬挂点。一个点如果在灯笼线上，那么它的悬挂点是自己。
那么什么时候原来的最短路不是答案呢？
那么就是对于任何的u和v，将它们连接起来后，新的最短路都比原来的最短路小。
换句话说:设灯笼线上的两个点x和y分别为准备新加边的u，v的悬挂点。那么只需比较(x到y的路径长度)和（ux，vy的长度和再加上每次询问时的那个值)即可。
（重头戏来了！)
如果上文的u和v再同一颗灯笼子树内呢？
（*）于是,你发现一个结论：如果一颗灯笼子树除悬挂点外有超过两个以上的节点，那么连接这颗灯笼子树内的两个没有直接边相连的点，无论询问多少，Ans会取到原图的最短路，也就是理论最大值。
所以，我们仅需考虑每颗颗灯笼子树除悬挂点外仅有1的点的原树即可。
由于要比较(x到y的路径长度)和（ux，vy的长度和再加上每次询问时的那个值），所以我们可以算出最大的(x到y的路径长度)-（ux，vy的长度和）,每次询问将其加上询问值并与0比较即可。
如何算出(x到y的路径长度)-（ux，vy的长度和）？将这个式子拆开分别维护，一遍dfs，用heap维护一下。建议读者自行撕烤这部分内容。
Code：
#include <cstdio>
#include <queue>
using namespace std;
const int S=600006;
struct info
{
int x;
long long s;
inline bool operator<(const info &a) const
{
return s<a.s;
}
}st[S];
priority_queue<info> pq;
int n,m,h[S],nx[S],v[S],w[S],eg=1,s[S],fa[S],top,lc[S],rc[S];
const long long infl=(1ll<<60)-1;
long long dep[S],res=-infl;
bool flag,mk[S];
void read(int &s)
{
s=0;char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
}
inline void egadd(int uu,int vv,int ww)
{
nx[++eg]=h[uu];h[uu]=eg;
v[eg]=vv;w[eg]=ww;
}
void dfs_1(int x)
{
s[x]=1;
for (int i=h[x];i;i=nx[i])
if (v[i]!=fa[x])
{
fa[v[i]]=x;
dep[v[i]]=dep[x]+w[i];
dfs_1(v[i]);
s[x]+=s[v[i]];
}
}
bool check()
{
int o=n;
if (s[o]>2) return false;
while (o!=1)
{
if (s[fa[o]]-s[o]>2) return false;
mk[o]=true;
o=fa[o];
}
mk[1]=true;
return true;
}
inline long long ma(long long a,long long b){return a>b?a:b;}
inline long long mi(long long a,long long b){return a<b?a:b;}
void dfs_3(int x)//这里是将原树转为二叉树，因为灯笼子树大小不超过两个点的树就是一颗二叉树
{
for (int i=h[x];i;i=nx[i])
if (v[i]!=fa[x])
{
dfs_3(v[i]);
if (mk[v[i]])
{
lc[x]=v[i];
break;
}
}
for (int i=h[x];i;i=nx[i])
if (v[i]!=fa[x])
if (!mk[v[i]])
{
rc[x]=v[i];
break;
}
}
void dfs_2(int x)
{
if (lc[x]) dfs_2(lc[x]);
if (rc[x]) dfs_2(rc[x]);
while (!pq.empty() && fa[pq.top().x]==x)
st[++top]=pq.top(),pq.pop();
if (!pq.empty()) res=ma(res,pq.top().s+dep[x]);
while (top) pq.push(st[top--]);
pq.push((info){x,2*(mk[x]?0:dep[x]-dep[fa[x]])-dep[x]});
}
int main()
{
read(n);read(m);
for (int i=1;i<n;i++)
{
int uu,vv,ww;
read(uu);read(vv);read(ww);
egadd(uu,vv,ww);
egadd(vv,uu,ww);
}
dfs_1(1);
flag=check();
if (flag) dfs_3(1),dfs_2(1);
int x;
while (m--)
{
read(x);
if (flag) printf("%lld
",dep[n]+mi(0,res+x));
else printf("%lld
",dep[n]);
}
return 0;
}