首先，肯定没有不合法情况（每条边的权值都赋值为 $1$ 就一定合法）
然后对于一条边 $(x,y)$ 来说，只可能有 3 种取值.
1. 取 $a[x]$
2. 取 $a[y]$
3. 取 $m$
然后转化成这一步后就可以进行树形 DP 了.
令 $f[x][0],f[x][1]$ 分别表示以 $x$ 为根的子树，且 $x$ 与 $x$ 父亲连边的边权小于等于 $a[x]$/大于 $a[x]$ 的最大权和.
这个裸做的话是一个 $O(n^2)$ 的树形背包.
但是我们发现这个问题中所有物品的体积都是 $1$，那么我们就可以先贪心选取一个儿子 $y$ 的最优决策点.
如果该决策点没有让边权小于等于 $a[x]$ ，就把差量扔进一个 set 里，贪心取出需要补齐的部分就行了.
代码：
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 500009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const ll inf=1000000000;
int n,m,edges;
ll f[N][2];
int deg[N];
int a[N],hd[N],to[N<<1],nex[N<<1];
void add(int u,int v) {
nex[++edges]=hd[u];
hd[u]=edges,to[edges]=v;
}
multiset<ll>se[N];
multiset<ll>::iterator it;
void dfs(int x,int ff) {
int det=deg[x]/2+1,cnt=0;
// f[x][0] : det-1
// f[x][1] : det
f[x][0]=f[x][1]=0;
for(int i=hd[x];i;i=nex[i]) {
int y=to[i];
if(y==ff) continue;
dfs(y,x);
ll cur=max(f[y][0]+a[y],f[y][1]+m);
f[x][0]+=cur;
f[x][1]+=cur;
if(a[x]>=a[y]) {
if(f[y][1]+m==cur&&m>a[x]) {
se[x].insert(-(max(f[y][0]+a[y],f[y][1]+a[x])-cur));
}
else ++cnt;
}
else {
se[x].insert(-(max(f[y][0]+a[x],f[y][1]+a[x])-cur));
}
}
int k0=det-1,k1=det;
if(cnt+se[x].size()>=k0) {
it=se[x].begin();
for(int i=1;i<=k0-cnt;++i) {
f[x][0]-=(*it);
it++;
}
}
else f[x][0]=-inf;
if(cnt+se[x].size()>=k1) {
it=se[x].begin();
for(int i=1;i<=k1-cnt;++i) {
f[x][1]-=(*it);
it++;
}
}
else f[x][1]=-inf;
se[x].clear();
if(deg[x]==1&&ff) {
f[x][0]=0;
f[x][1]=-inf;
}
}
int main() {
// setIO("input");
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
a[i]=min(a[i],m);
}
int x,y,z;
for(int i=1;i<n;++i) {
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
++deg[x];
++deg[y];
}
dfs(1,0);
printf("%lld
",f[1][1]);
return 0;
}