题目传送门

Description

自从 Y 君退役之后,她就迷上了吃鸡,于是她决定出一道吃鸡的题。

Y 君将地图上的所有地点标号为 $1$ 到 $n$,地图中有 $n − 1$ 条双向道路连接这些点,通过一条双向道路需要一定时间,保证从任意一个点可以通过道路到达地图上的所有点。

有些点上可能有资源,Y 君到达一个有资源的点后,可以选择获取资源来使自己的武力值增加 $w_i$ ,也可以选择不获取资源。如果 Y 君获取了一个点上的资源,这个点上的资源就会消失,获 取资源不需要时间。

有些点上可能有敌人,Y 君到达一个有敌人的点后,必须花费 $t_i$ 秒伏地与敌人周旋,并最终将敌人消灭。如果 Y 君消灭了一个点上的敌人,这个点上的敌人就会消失。Y 君不能无视敌人继 续前进,因为这样会被敌人攻击。

如果一个点上既有资源又有敌人,Y 君必须先消灭敌人之后才能获取资源,否则就会被敌人突袭。

游戏开始时,Y 君可以空降到任意一个点上,接下来,她有 T 秒进行行动,T 秒后她就必须 前往中心区域送快递。Y 君希望她前往中心区域送快递时,武力值尽可能大,请你帮助 Y 君设计 路线,以满足她的要求。你只需输出 T 秒后 Y 君的武力值。

Solution

毒瘤好的一道树形DP。

设 $f_{i,j}$ 表示在以 $i$ 为根的子树中,花了 $j$ 的时间,最终回到 $i$ 的最大分数。

设 $g_{i,j}表示在 以 $i$ 为根的子树中,花了 $j$ 的时间,最终不一定回到 $i$ 的最大分数。

考虑 $f$ 如何转移。

从 $i$ 出发,走 $son$ 之前的子树,回到 $i$ ,然后又去 $son$ 子树中转一圈,最终转回到 $i$ 。

$$f[i][j] \Leftarrow \max \{ f[i][k] + f[ j-k-2\times dis[i][son] \}$$

减去两倍的 $dis[i][son]$ ,原因是要走回来。

接下来想 $g$ 。

这个情况有两种,分别是:

1.从 $i$ 出发,走 $son$ 之前的子树,回到 $i$ ,然后又去 $son$ 子树中,永远地留在 $son$ 子树里。

$$ g[i][j] \Leftarrow f[i][k] + g[son][j-k-dis[i][son]] $$

2.从 $i$ 出发,走 $son$ 和 $son$ 之前的子树,其中在 $son$ 子树中转了一圈后回来。最终,在 $i$ 点或 $son$ 之前的子树中停下来。也就是说, $son$ 子树只是作为一个中转站,转过一圈之后走出来,然后到别处停下来。

$$ g[i][j] \Leftarrow f[son][k] + g[i][j-k-2\times dis[i][son]] $$

知道了 $f$ 和 $g$ ,那就可以算出从根开始的最优解,即 $\max g[root][j]$ 。

所以我们可以枚举根,然后对于每个根做一遍树形DP。

时间复杂度 $O(n^2T^2)$ ,显然过不了。

我们之前求的是从根出发,那么不妨思考一下,在这个子树中,不一定会从根节点出发的情况。

设 $h_{i,j}$ 表示在以 $i$ 为根的子树中,花了 $j$ 的时间,从 $i$ 子树中的某个点出发,经过 $i$ 点,最终在 $i$ 子树中停下来。

1.将 $i$ 以及 $son$ 之前的子树求出的 $g$ 值,$son$ 里面的子树求出的 $g$ 值,合并在一起。

怎么理解呢?形象地理解一下,$f$ 、$g$ 、$h$ 值就像是条绳子所作出的贡献。其中 $f$ 至少两端在根节点上,$g$ 至少一端在根节点上,$h$ 的端点可以不再根节点上。而这样合并就是将两条 $g$ 绳各自的一头接在了一起,形成一个新的 $h$ 绳。

$$ h[i][j]\Leftarrow g[i][k]+g[son][j-k-dis[i][son]]$$

2.将 $i$ 的 $h$ 绳中,插入新的一段 $son$ 的 $f$ 绳。这样就可以保证插入之后绳子没有中断。

$$ h[i][j] \Leftarrow f[i][k]+h[son][j-k-2\times dis[i][son]]$$

3.和上面类似,在 $son$ 的 $h$ 绳中,插入新的一段 $i$ 以及 $son$ 之前子树的 $f$ 绳。

$$ h[i][j] \Leftarrow h[i][k]+f[son][j-k-2\times dis[i][son]] $$

这样求出所有的 $h$ 值,这样,答案即 $\max h_{i,j}$

对了,需要格外注意一下转移的顺序,按照 $h$ 、$g$ 、$f$ 的顺序(不然可能会出现叠加),还有一个六年级的同学都应该知道的 $j$ 要倒着枚举。

时间复杂度 $O(nT^2)$ ,可以过。

Code

/*
 * @Name: 110774
 * @Author: Lovely_XianShen
 * @Date: 2019-11-05 09:20:58
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>

using namespace std;

int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar())if (ch == '-')f = -1;
    for (; isdigit(ch); ch = getchar())x = x * 10 + ch - '0';
    return x * f;
}

const int N = 305;

int n, f[N][N], g[N][N], h[N][N], t[N], w[N], T, ans;

int head[N], tot;

struct edg {
    int to, nxt, val;
} e[N << 1];

inline void add(int x, int y, int z) {
    e[++tot].to = y;
    e[tot].val = z;
    e[tot].nxt = head[x];
    head[x] = tot;
}

inline void chkmax(int &x, const int &y) {
    if (x < y) x = y;
    return;
}

void dfs(int x, int fa) {
    if (t[x] > T)
        return;
    f[x][t[x]] = g[x][t[x]] = h[x][t[x]] = w[x];
    for (int a = head[x]; a; a = e[a].nxt) {
        int to = e[a].to;
        if (to == fa)
            continue;
        dfs(to, x);
        for (int i = T; i >= t[x]; i--) {
            for (int j = i - e[a].val; j >= t[x]; j--) {
                int ff = f[x][j], gg = g[x][j], hh = h[x][j];
                int k = i - j - e[a].val;
                if (k >= t[to] ) {
                    chkmax(g[x][i], ff + g[to][k]);
                    chkmax(h[x][i], gg + g[to][k]);
                }
                k -= e[a].val;
                if (k >= t[to]) {
                    chkmax(f[x][i], ff + f[to][k]);
                    chkmax(g[x][i], gg + f[to][k]);
                    chkmax(h[x][i], hh + f[to][k]);
                    chkmax(h[x][i], ff + h[to][k]);
                }
            }
            chkmax(ans, h[x][i]);
        }
    }
    return;
}

int main() {
    n = read();
    T = read();
    for (int i = 1; i <= n; i++)
        w[i] = read();
    for (int i = 1; i <= n; i++)
        t[i] = read();
    for (int i = 1; i < n; i++) {
        int x, y, z;
        x = read();
        y = read();
        z = read();
        add(x, y, z);
        add(y, x, z);
    }
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}