。。 好题。。无限仰慕宋神牛。。。

首先：
节点数-高度 ≤ 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]);
}

Posted by xiaodao
Category: 日常