HDU 5534 Partial Tree：樹度數分配的完全背包模型

題意

構造 n 個節點的樹，f[i] 表示度數（入度+出度）為 i 的節點權值。求樹的最大總權值。

模型轉化

• n 個節點的樹共 n-1 條邊，總度數 = 2(n-1)。
• 每個節點至少度數 1，預分配 n 個度數，剩餘 n-2 個度數自由分配。
• 問題等價於：將 n-2 個「額外度數」分配給節點，每個節點可獲得 0..n-2 額外度數，獲得 k 額外度數的節點最終度數為 k+1，權值增量為 f[k+1] - f[1]。
• 這正是完全背包：物品為「額外度數 1,2,…,n-2」，價值為對應權值增量，背包容量 n-2，求最大價值。

DP 方程

dp[j] = max(dp[j], dp[j-i] + f[i+1] - f[1])，最終答案 dp[n-2] + n*f[1]。代碼中直接用 f[i+1] 作為物品價值，初始 dp[0]=0，最後加上基礎權值 n*f[1]（或直接累加）。

代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int f[2020], dp[4050];
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i=1;i