Vijos 1676. 淘淘吃蘋果

。。 好題。。無限仰慕宋神牛。。。

首先:
節點數-高度 ≤ k

什麼意思呢?

就是背包容量為 k。。。然後其中一條鏈可以免費取。。。
。。設這條鏈為 free chain 。然後就可以 O(n3) 了。。。

g[u][i]:
以 u 為根的子樹。。。
容量為 i。。。

f[u][i]:
以 u 為根的子樹。。u 在 free chain 上。。
容量為 i。。。

https://vijos.org/records/5411e2a348c5fc1e1c8b4568

我們發現 g[][] 就是選課。。。https://vijos.org/records/54062d6048c5fcbb348b4568
經過 doc 的指導。。。我已經指導這種樹形背包是可以用 dfs 序。優化到 O(n2) 的。。。

這個步驟還是 rather subtle。。。。具體說來。。就是

g[u][i] / f[u][i] 現在表示。。。從根結點 0 開始,所有 dfs 序 <= r[u] 的結點。。。 (r[u]。。離開時刻。。也就是 u 的子樹加之前訪問過的結點)。。。 初始時: f[v][i] = max(g[u][i], i ? f[u][i-1] : 0) + val[v]; 左邊表示 free_chain 連接到 v。。 右邊表示 free_chain 不經過 v。。。 (這裡更 subtle 了。。。因為 f[v] 表示無論如何。。free_chain 都經過 r->u->v 的。。
。。。我們想得到 free_chain 不經過 v 的轉移。。就得通過在初始化時就減少一格容量。。)

https://vijos.org/records/5411fad048c5fcd2208b4568

//}/* .................................................................................................................................. */


const int N = int(4e3) + 9;


VI adj[N]; LL g[N][N], f[N][N], val[N];
int n, m;


void dfs(int u = 0, int m = ::m){


    ECH(it, adj[u]){
        int v = *it;


        REP(i, m+1){
            g[v][i] = g[u][i] + val[v];
            f[v][i] = max(g[u][i], i ? f[u][i-1] : 0) + val[v];
        }


        dfs(v);


        REP(i, m+1){
            if (i) checkMax(g[u][i], g[v][i-1]);
            checkMax(f[u][i], f[v][i]);
        }
    }
}


int main(){


#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif


    REP_1_C(i, RD(n, m)){
        adj[RD()].PB(i);
        RD(val[i]);
    }


    dfs();
    OT(f[0][m]);
}