適用于合并操作復雜度較高，而插入操作復雜度較低的場景。

P6326 Shopping

在分析題目時，我們發現題目的本質等價于在樹中選取一個連通塊。

首先，將完全背包問題利用二進制拆分處理，再探索多種簡化策略，最終確定了有效的解決方案。下面介紹一種基于動態規劃（DP）的思路。

方法一：點分治 + dfn 序列

參考百家博等人的思路，主要步驟如下：

1. 問題轉化：樹上背包問題通常不如序列背包問題高效，因此可以嘗試將樹轉化為序列。注意，一個節點及其子樹在 DFS 得到的 dfn 序列中通常是連續的。
2. 選取根節點：任選一個根節點，并保證該根至少選擇一個物品。
3. 構造 dfn 序列并逆序 DP：利用 DFS 得到的 dfn 序列，由于序列后面的節點不可能是前面節點的祖先，可以采用逆序 DP 來進行狀態轉移。

設定如下變量：

• \(siz[i]\)：以 \(i\) 為根的子樹大小。
• \(dp[i][j]\)：在 dfn 序列中，從第 \(i\) 個節點開始，當總花費不超過 \(j\) 時所能獲得的最大價值。

狀態轉移分析：

• 不選方案：不選取以 \(i\) 為根的子樹，此時有 \(dp[i][j] = dp[i+siz[i]][j]\)。
• 選取方案：選擇以 \(i\) 為根的子樹，必須至少選中一個物品，通過多重背包思想更新 \(dp[i][j]\)。

最終答案由 \(dp[1][j]\) 的最大值確定，其中索引 1 對應樹的根。

該方法單次 DP 的時間復雜度為 \(O(nm\log m)\)，但由于需要對每個節點作為根進行處理，總體復雜度為 \(O(n^2m\log m)\)。相比直接在樹上求解（\(O(nm^2\log m)\)）已經有所提升，但仍有優化空間。

進一步地，由于題目要求選取的是樹上連通塊，可以直接采用點分治策略將時間復雜度降低至 \(O(nm\log n\log m)\)，從而滿足較大數據規模的要求（注意測試數據較多）。

示例代碼

在編碼過程中，常見錯誤包括：

• 01 背包中正向枚舉導致錯誤；
• 狀態轉移時容易將 \(dp[i+siz[dfn[i]]\) 錯寫為 \(dp[i+siz[i]]\)。

以下為主要代碼實現：

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int Size = (1<<20) + 1;
char buf[Size], *p1 = buf, *p2 = buf;
char buffer[Size];
int op1 = -1;
const int op2 = Size - 1;
#define getchar() (tt == ss && (tt=(ss=In)+fread(In, 1, 1<<20, stdin), ss == tt) ? EOF : *ss++)
char In[1<<20], *ss = In, *tt = In;

inline int read() {
    int x = 0, c = getchar(), f = 0;
    for(; c > '9' || c < '0'; f = (c=='-'), c = getchar());
    for(; c >= '0' && c <= '9'; c = getchar())
        x = (x << 1) + (x << 3) + (c ^ 48);
    return f ? -x : x;
}

inline void write(int x) {
    if(x < 0) x = -x, putchar('-');
    if(x > 9) write(x/10);
    putchar(x % 10 + '0');
}

const int N = 505;
vector<int> v[N], E[N];
int n, m;
int w[N], c[N], d[N];

void chai(int id, int x) {
    if(!x) return;
    v[id].clear();
    for(int k = 0;; k++) {
        int nw = 1ll << k;
        if(nw > x) {
            nw >>= 1;
            v[id].pop_back();
            v[id].push_back(x - nw + 1);
            return;
        }
        v[id].push_back(nw);
    }
}

bool vis[N];
int siz[N];

pair<int,int> findG(int p, int fa, int tot) {
    pair<int,int> nw = make_pair(tot - siz[p], p), ans = make_pair(n+1, -1);
    for(int to : E[p]) {
        if(to == fa || vis[to]) continue;
        ans = min(ans, findG(to, p, tot));
        nw.first = max(nw.first, siz[to]);
    }
    return min(ans, nw);
}

void dfs(int p, int fa) {
    siz[p] = 1;
    for(int to : E[p]) {
        if(to == fa || vis[to]) continue;
        dfs(to, p);
        siz[p] += siz[to];
    }
}

int tot, id[N];
int dp[N][4005];

void dfs1(int p, int fa) {
    siz[p] = 1;
    id[++tot] = p;
    for(int to : E[p]) {
        if(to == fa || vis[to]) continue;
        dfs1(to, p);
        siz[p] += siz[to];
    }
}

int ans = 0;

void dodp(int root) {
    tot = 0;
    dfs1(root, 0);
    for(int i = 1; i <= tot + 1; i++) memset(dp[i], 0, sizeof(dp[i]));
    for(int i = tot; i >= 1; i--) {
        int p = id[i];
        for(int j = c[p]; j <= m; j++)
            dp[i][j] = dp[i + 1][j - c[p]] + w[p];
        for(int cnt : v[p]) {
            int V = cnt * c[p], W = cnt * w[p];
            for(int j = m; j >= V; j--)
                dp[i][j] = max(dp[i][j], dp[i][j - V] + W);
        }
        for(int j = 1; j <= m; j++)
            dp[i][j] = max(dp[i][j], dp[i + siz[p]][j]);
    }
    for(int i = 1; i <= m; i++) ans = max(ans, dp[1][i]);
}

void solve(int root) {
    vis[root] = true;
    for(int to : E[root]) {
        if(vis[to]) continue;
        dfs(to, 0);
        int nxt = findG(to, 0, siz[to]).second;
        solve(nxt);
    }
    dodp(root);
    vis[root] = false;
}

void solve() {
    n = read();
    m = read();
    for(int i = 1; i <= n; i++) w[i] = read();
    for(int i = 1; i <= n; i++) c[i] = read();
    for(int i = 1; i <= n; i++) d[i] = read();
    for(int i = 1; i <= n; i++) {
        chai(i, d[i] - 1);
        E[i].clear();
    }
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1, 0);
    int root = findG(1, 0, siz[1]).second;
    solve(root);
    cout << ans << "\n";
    ans = 0;
}

signed main() {
    int T = read();
    while(T--) solve();
    return 0;
}

方法二：樹上啟發式合并

（內容待更新）