D
考虑树形DP，记\(f[u],g[u]\)分别为最终回到u/停在子树中的最晚第一次到达u的时间。原本以为在枚举了最后一个的情况下，遍历子树的顺序是以f升序的，（因为只有最后一个不对后面产生影响）；但实际上很假，因为在去掉最后一个后，倒数第二个也成了最后一个，那么针对最后一个的特殊情况也同样会出现。
这时候应该用经典的贪心不等式，列出最简化的情况的式子（只有两个子树）：
\(min(f1,f2-2*sz1)\ge min(f2,f1-2*sz2)\)
然后分讨，发现第二个min如果取f1必然不成立，然后取另一个就可以得到：
\(f1-2*sz1 \le f2-2*sz2\)
然后经过一些经典的证明可以推广到整个序列，所以按照这个排序即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,inf=2e9+5+N;
void Min(int& x,int y){
if(y<x) x=y;
}
void Max(int& x,int y){
if(y>x) x=y;
}
int hd[N],to[N<<1],nx[N<<1],tt;
void add(int u,int v){
nx[++tt]=hd[u];
to[hd[u]=tt]=v;
}
int n,k,a[N],f[N],g[N],sz[N],sn[N],h[N],Mn[N],su[N];
bool cmp(int x,int y){
return f[x]+2*sz[x]<f[y]+2*sz[y];
}
void dfs(int u,int fa){
sz[u]=1;
for(int e=hd[u];e;e=nx[e]) if(to[e]!=fa){
int v=to[e];
dfs(v,u);
sz[u]+=sz[v];
}
int m=0;
for(int e=hd[u];e;e=nx[e]) if(to[e]!=fa) sn[++m]=to[e];
if(!m){
f[u]=min(a[u],a[u]+k-2*(sz[u]));
g[u]=a[u];
return;
}
sort(sn+1,sn+m+1,cmp);
f[u]=g[u]=-inf;
for(int i=1;i<=m;i++) su[i]=su[i-1]+sz[sn[i]],h[i]=f[sn[i]]-2*su[i-1]-1;
Mn[m+1]=inf;
for(int i=m;i;i--) Mn[i]=min(Mn[i+1],h[i]);
int mn=inf;
for(int i=1;i<=m;i++){
Max( f[u],min(h[i]-(su[m]-su[i])*2,min(Mn[i+1]+sz[sn[i]]*2,mn)) );
Max(g[u],min( min(a[u]+k-2*(sz[u]-sz[sn[i]]),g[sn[i]]-2*(sz[u]-sz[sn[i]]-1)-1),min(Mn[i+1]+sz[sn[i]]*2,mn) ) );
Min(mn,h[i]);
}
Min(f[u],min(a[u],a[u]+k-2*(sz[u])) );
Min(g[u],a[u]);
//printf("u=%d f=%d g=%d\n",u,f[u],g[u]);
}
int main()
{
cin>>n>>k;
for(int u,v,i=1;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(1,0);
if(g[1]<0) puts("-1");
else cout<<g[1]<<endl;
return 0;
}