Link.
先对深度离散化，将答案转化为原本为黑点现在为白点的位置个数。
进行树形 dp 的时候遇到黑点可以选择先提起来在子树外放置（提黑点数加一），遇到白点的时候可以选择用子树外的黑点交换（提黑点数减一）。
设 \(f_{u,j,k}\) 表示 \(u\) 子树内没有全部覆盖，最大未覆盖点深度为 \(j\)，答案为 \(k\) 的最大提黑点数（答案和提黑点数状态与值交换原因为两者大小后者更大）；\(g_{u,j,k}\) 表示 \(u\) 子树内全部覆盖，最小黑点深度为 \(j\)，答案为 \(k\) 的最大提黑点数。
考虑初值：
-
若 \(col_u=1\)，则 \(f_{u,dep_u,1}=1,g_{u,dep_u,0}=0\)。
-
若 \(col_u=0\)，则 \(f_{u,dep_u,0}=0,g_{u,dep_u,0}=-1\)。
考虑转移，下文称 \(dep_u=d\)：
-
\(f_{u,j,k}+f_{v,j1,k1} \to f_{u,\max(j,j1),k+k1}\)
-
\(f_{u,j,k}+g_{v,j1,k1} \to f_{u,j,k+k1} (Dep_j+Dep_{j1}-2 Dep_d > x)\)
-
\(f_{u,j,k}+g_{v,j1,k1} \to g_{u,j1,k+k1} (Dep_j+Dep_{j1}-2 Dep_d \le x)\)
-
\(g_u + f_v\) 同上
-
\(g_{u,j,k}+g_{v,j1,k1} \to g_{u,\min(j,j1),k+k1}\)
第一维加第三维树形背包为 \(n^2\)，第二维用前缀和优化做到 \(O(1)\) 转移，总时间复杂度 \(O(n^3)\)，使用 short 存储。
#include <bits/stdc++.h>
using namespace std;
#define ll long longconst int N=505;int n,k,idx;
int head[N],nxt[N<<1],ver[N<<1],val[N<<1];inline int read(){int t=0,f=1;register char c=getchar();while(c<'0'||c>'9') f=(c=='-')?(-1):(f),c=getchar();while(c>='0'&&c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();return t*f;
}void add(int u,int v,int w){nxt[++idx]=head[u];head[u]=idx;ver[idx]=v;val[idx]=w;
}int len;
int col[N];ll dep[N],Dep[N];void dfs(int u,int v){for(int i=head[u];i;i=nxt[i]){int dao=ver[i];if(dao==v) continue;dep[dao]=dep[u]+val[i],Dep[dao]=dep[dao];dfs(dao,u);}
}int siz[N];short f[N][N][N>>1],g[N][N][N>>1];
short fp[2][N][N>>1],fn[2][N][N>>1],gp[2][N][N>>1],gn[2][N][N>>1];void Max(short &x,short y){x=max(x,y);}void init(int u,bool p){for(int i=0;i<=min(n/2,siz[u]);i++){fp[p][0][i]=-n,gp[p][0][i]=-n,fn[p][len+1][i]=-n,gn[p][len+1][i]=-n;for(int j=1;j<=len;j++)fp[p][j][i]=max(fp[p][j-1][i],f[u][j][i]),gp[p][j][i]=max(gp[p][j-1][i],g[u][j][i]);for(int j=len;j>=1;j--)fn[p][j][i]=max(fn[p][j+1][i],f[u][j][i]),gn[p][j][i]=max(gn[p][j+1][i],g[u][j][i]);}
}short f1[N][N>>1],g1[N][N>>1];void Merge(int u,int dao){for(int i=min(n/2,siz[u]+siz[dao]);i>=0;i--){for(int j=dep[u];j<=len;j++) f1[j][i]=-n,g1[j][i]=-n;for(int j1=min(i,siz[u]);j1>=0;j1--){if(i-j1>siz[dao]) break;int j2=i-j1,p=len+1;for(int j=dep[u];j<=len;j++){while(p>1&&Dep[p-1]>2*Dep[dep[u]]+k-Dep[j]) p--;Max(f1[j][i],f[u][j][j1]+gn[1][p][j2]);Max(f1[j][i],gn[0][p][j1]+f[dao][j][j2]);Max(g1[j][i],fp[0][p-1][j1]+g[dao][j][j2]);Max(g1[j][i],g[u][j][j1]+fp[1][p-1][j2]);Max(f1[j][i],fp[0][j][j1]+f[dao][j][j2]);Max(f1[j][i],f[u][j][j1]+fp[1][j][j2]);Max(g1[j][i],g[u][j][j1]+gn[1][j][j2]);Max(g1[j][i],gn[0][j][j1]+g[dao][j][j2]);}}for(int j=dep[u];j<=len;j++) f[u][j][i]=f1[j][i],g[u][j][i]=g1[j][i];}siz[u]+=siz[dao];
}void dfs1(int u,int v){siz[u]=1;if(col[u]) f[u][dep[u]][1]=1,g[u][dep[u]][0]=0;else f[u][dep[u]][0]=0,g[u][dep[u]][0]=-1;for(int i=head[u];i;i=nxt[i]){int dao=ver[i];if(dao==v) continue;dfs1(dao,u);init(u,0);init(dao,1);Merge(u,dao);}
}signed main(){n=read(),k=read();for(int i=1;i<=n;i++) col[i]=read();for(int i=1;i<n;i++){int u=read(),v=read(),w=read();add(u,v,w),add(v,u,w);}dfs(1,0);sort(Dep+1,Dep+1+n);len=unique(Dep+1,Dep+1+n)-(Dep+1);for(int i=1;i<=n;i++)dep[i]=lower_bound(Dep+1,Dep+1+len,dep[i])-Dep;memset(f,-0x3f,sizeof(f));memset(g,-0x3f,sizeof(g));dfs1(1,0);for(int j=0;j<=n/2;j++)for(int i=1;i<=len&&Dep[i]<=k;i++)if(g[1][i][j]>=0){cout<<j<<"\n";return 0;}cout<<-1<<"\n";return 0;
}