题解 P4657 【[CEOI2017]Chase】

ModestCoder_ · 2020-11-30 09:05:29 · 题解

扔磁铁得到的收益有两种情况

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

所以一条路径上，扔磁铁获得的收益有两种情况

而且我们可以发现，假如我从某一个点出发，一定要扔一个磁铁。或者说，我扔第一个磁铁的地方，一定是出发点

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

从u的子树中某点出发，往上走经过u，再走向子树中的某点

保证了不重不漏

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

令

以u为中转点的答案统计

转移

还发现其实我是从子树中选了两个方向，一个是来时的方向，一个是去向

因为方向不同，起点的贡献就不同，所以我还有倒着枚举儿子枚举一遍

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;
}