思路与算法

后序合并每个包含根u的连通访问区域。DP按总时间及0、1、2个自由行程端点分类，其他端点视为u；初始访问u需付敌人时间并取得资源。合并孩子时可跳过，或加入孩子方案；孩子恰有1个自由端点时跨边一程，否则往返，合并后自由端点总数不超过2。对所有子树、时间和端点状态取最大收益。

正确性说明

树上访问区域必连通。固定两个行程端点时，端点间路径边经过一次，其余访问边至少往返一次，深度遍历可达到该下界。合并中孩子恰含一个自由端点等价该边位于端点路径；含0或2个时均应往返。状态记录节点一次性敌人费用和资源，孩子合并不重复，所有合法访问区域与端点配置均被覆盖。任意访问区域的最高祖先会成为某次取优的根。

复杂度

每条父子合并枚举两个时间及常数个端点状态，最坏O(nT²)，初始化O(nT)，空间O(nT)上界；已并入的孩子表释放。T≤300。

易错点

孩子有两个自由端点时跨父边仍需往返，不能错减为0。空降点也必须先消灭敌人；时间不足的节点不可访问。资源非负，访问后取走不会变差；道路与敌人均可为0时间。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, T;
    cin >> n >> T;
    vector<int> w(n), t(n);
    for (int &x : w)
        cin >> x;
    for (int &x : t)
        cin >> x;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 1, u, v, c; i < n; i++) {
        cin >> u >> v >> c;
        --u;
        --v;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    vector<int> par(n, -1), ord(1, 0);
    for (int i = 0; i < n; i++)
        for (auto e : g[ord[i]])
            if (e.first != par[ord[i]]) {
                par[e.first] = ord[i];
                ord.push_back(e.first);
            }
    using D = vector<array<int, 3>>;
    vector<D> dp(n);
    int ans = 0;
    const int NEG = -1000000000;
    for (int z = n - 1; z >= 0; z--) {
        int u = ord[z];
        D f(T + 1, array<int, 3>{NEG, NEG, NEG});
        if (t[u] <= T)
            f[t[u]] = {w[u], w[u], w[u]};
        for (auto e : g[u])
            if (par[e.first] == u) {
                int v = e.first, c = e.second;
                D h = f;
                for (int i = 0; i <= T; i++)
                    for (int a = 0; a <= 2; a++)
                        if (f[i][a] >= 0)
                            for (int b = 0; a + b <= 2; b++) {
                                int ec = (b == 1 ? c : 2 * c);
                                for (int j = 0; i + j + ec <= T; j++)
                                    if (dp[v][j][b] >= 0)
                                        h[i + j + ec][a + b] =
                                            max(h[i + j + ec][a + b], f[i][a] + dp[v][j][b]);
                            }
                f.swap(h);
                dp[v].clear();
            }
        for (auto a : f)
            for (int v : a)
                ans = max(ans, v);
        dp[u] = move(f);
    }
    cout << ans << '\n';
}