题解

思路概述

• 把树随便定根。逃亡者走过的路径不会出现重复的边，因此是一条简单路径。若我们约定路径在根方向的最上端结点为“起点”、最下端结点为“终点”，那么这条路径可拆成两段：自上而下的一段，以及自下而上的一段。两段在根本质相同——经过某个结点时可以选择是否投放磁铁，从而把该结点相邻房间的铁球全部吸到当前结点。
• 设 f[u][k] 表示路径从结点 u 向下走入某个子树并最终离开该子树（不会回到父亲）时，在这段路径上使用了 k 个磁铁所能取得的最大收益差；g[u][k] 表示路径从子树走到 u 并继续向上离开 u（沿父边离开）时的最大收益差。这样一来，一条完整的路径可以在某条边处拆分成 “父亲往下的一段” 与 “孩子往上的一段”，从而枚举磁铁数量的划分来更新全局答案。
• 为了便于计算磁铁所带来的收益，先预处理 b[u] = Σ F_v（所有与 u 相邻结点的铁球数量）。当逃亡者在 u 放置磁铁后，追逐者会在经过 u 时额外遭遇这些铁球，而逃亡者自己只会受到 F_u 的阻碍，上述 DP 转移中的 b[u] - F_v 等项正是描述“在某条边处决定吸球”的收益变化。

实现细节

• DFS 过程中，先对子结点递归，拿到 f[v][·] 与 g[v][·] 后再更新父亲。枚举磁铁个数 i，尝试把当前子树接在父亲的路径两端，更新 ans。同时用子树的状态刷新父亲的 f[u][·] 与 g[u][·]：要么整个最佳段完全在子树内，要么在子树里放最后一个磁铁再衔接到父亲。
• 由于磁铁个数上限 $V \le 100$，直接枚举 i 与 m-i 即可，双重循环复杂度可接受。
• 初始时 f[u][1] = b[u]，表示仅访问 u 并在此投放一个磁铁的收益。全局答案在 DFS 中实时维护。

复杂度

枚举每条边时要遍历最多 V 种磁铁分配，故时间复杂度 $O(nV)$，空间复杂度同为 $O(nV)$。

#include<cstdio>
const int MAXN=100007;
#define max(x,y) ((x)>(y)?(x):(y))
#define Max(x,y,z) max(max(x,y),z)
long long ans,b[MAXN],f[MAXN][107],g[MAXN][107];
int n,m,a[MAXN],h[MAXN],e[MAXN<<1],nxt[MAXN<<1],idx=0;
inline void add(int &u,int &v){
	e[idx]=v;
	nxt[idx]=h[u];
	h[u]=idx;
	++idx;
}
void DFS(int u,int fa){
	f[u][1]=b[u];
	for(int y=h[u],v;~y;y=nxt[y]){
		if((v=e[y])==fa){
			continue;
		}
		DFS(v,u);
		for(int i=1;i<m;++i){
			ans=Max(ans,f[u][m-i]+max(g[v][i],g[v][i-1]+b[v]-a[u]),g[u][m-i]+max(f[v][i],f[v][i-1]+b[u]-a[v]));
		}
		for(int i=1;i<=m;++i){
			ans=max(ans,f[u][i]=Max(f[u][i],f[v][i],f[v][i-1]+b[u]-a[v]));
			g[u][i]=Max(g[u][i],g[v][i],g[v][i-1]+b[v]-a[u]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	for(int u=1;u<=n;++u){
		for(int i=h[u];~i;i=nxt[i]){
			b[u]+=a[e[i]];
		}
	}
	DFS(1,0);
	printf("%lld",ans);
	return 0;
}