【题解】LuoGu4657：[CEOI2017]Chase

原题传送门
扔磁铁得到的收益有两种情况

1. 我在起点，扔一个磁铁，周围的权值是收益，因为周围的那些铁块我肯定不会遇到，而追逐者肯定会遇到
2. 我从某一个点走过来，假设上一个点是红点，现在我在绿点，然后我扔了一个磁铁，我获得的收益是周围点的权值和减去红点的权值，因为我是经过了红点的，遇到过红点的铁块，而且追逐者也肯定会遇到

所以一条路径上，扔磁铁获得的收益有两种情况
而且我们可以发现，假如我从某一个点出发，一定要扔一个磁铁。或者说，我扔第一个磁铁的地方，一定是出发点

思考树形dp，遍历到某个点$u$的时候，计算如下图的最优值

从$u$的子树中某点出发，往上走经过$u$，再走向子树中的某点
保证了不重不漏

所以我是钦定了从起点走到终点是先往上走再往下走，而这道题目，起点扔磁铁的贡献与中途某一点扔磁铁的贡献的计算方式是不同的。所以我设计状态的时候需要着重考虑

令
$a[u]$为该点权值
$s[u]$为与该点相邻的所有点权值和
$f[u][i]$表示从$u$的子树中出发往上走到$u$，共扔了$i$个磁铁的最优值
$g[u][i]$表示从$u$往下走到子树中某一点，共扔了$i$个磁铁的最优值
初始化$f[u][1]=s[u](u为起点)$
$g[u][1]=s[u]-a[pre](u为往下走的过程中的一个点)$
以$u$为中转点的答案统计
$ans=max(ans,f[u][i]+g[v][m-i])$
转移
$f[u][i]=max(f[u][i],f[v][i],f[v][i-1]+s[u]-a[v])$
$g[u][i]=max(g[u][i],g[v][i],g[v][i-1]+s[u]-a[pre])$

还发现其实我是从子树中选了两个方向，一个是来时的方向，一个是去向
因为方向不同，起点的贡献就不同，所以我还有倒着枚举儿子枚举一遍

Code：

#include <bits/stdc++.h>
#define maxn 100010
#define maxm 110
#define LL long long
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], n, m, stk[maxn];
LL a[maxn], s[maxn], f[maxn][maxm], g[maxn][maxm], ans;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){
	edge[++num] = (Edge){y, head[x]}, head[x] = num;
}

void dfs(int u, int pre){
	for (int i = 1; i <= m; ++i)
		f[u][i] = s[u], g[u][i] = s[u] - a[pre];
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v == pre) continue;
		dfs(v, u);
		for (int j = 0; j <= m; ++j) ans = max(ans, f[u][j] + g[v][m - j]);
		for (int j = 1; j <= m; ++j){
			f[u][j] = max(f[u][j], max(f[v][j], f[v][j - 1] + s[u] - a[v]));
			g[u][j] = max(g[u][j], max(g[v][j], g[v][j - 1] + s[u] - a[pre]));
		}
	}
	for (int i = 1; i <= m; ++i)
		f[u][i] = s[u], g[u][i] = s[u] - a[pre];
	int top = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v == pre) continue;
		stk[++top] = v;
	}
	while (top){
		int v = stk[top--];
		for (int j = 0; j <= m; ++j) ans = max(ans, f[u][j] + g[v][m - j]);
		for (int j = 1; j <= m; ++j){
			f[u][j] = max(f[u][j], max(f[v][j], f[v][j - 1] + s[u] - a[v]));
			g[u][j] = max(g[u][j], max(g[v][j], g[v][j - 1] + s[u] - a[pre]));
		}
	}
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read();
		addedge(x, y), addedge(y, x);
		s[x] += a[y], s[y] += a[x];
	}
	dfs(1, 0);
	printf("%lld\n", ans);
	return 0;
}