蓝桥杯 强力党逗志芃 链式前向星结构的树形dp

// 蓝桥杯 强力党逗志芃// 采用树形dp，树以链式前向星形式存储#include <iostream>using namespace std;int power[205]; // 存每个技能的强度int cnt = 0; // 边的编号，从1记起int head[205]; // head[i] == 以i为父节点的所有边中，编号最大的边的编号，默认初始化为 0，也就是没有一条边以i为父节点int n, m; // 含义如题int ans[205][205]; //树形dp用到的数组，ans[i][j] == 以i为根节点，发展j个技能能达到的最大power值struct edge { // 存边的结构体，v是边连接的子节点，u是边连接的父节点(不会直接用到所以不存)，next是同样以u为父节点的上一条边的编号int v;int next;} edges[205];void add_edge(int u, int v) { // 顾名思义，这是加入边的函数edges[++cnt].v = v;edges[cnt].next = head[u];head[u] = cnt;}// treedp函数要干的就是寻找以root为根节点，给0, 1, 2, ..., m个技能点能得到的最大power, 也就是ans[root][0], ..., ans[root][m]void treedp(int root) {for(int i=head[root] ;i>0; i=edges[i].next) { // 遍历以root为依赖的子技能, i是root上的边的编号, 如果root是叶子节点便会直接跳过这个循环, 在// 下一个循环中计算ans[root][i] = power[root] (i != 0) 即认为向叶子节点分配 >= 1个技能点，能达到的最大值都是power[root]int v = edges[i].v;treedp(v);// 下面两个循环很细节，慢慢理解for(int k=m;k>0;k--) { //求ans[root][k], for(int h=k;h>0;h--) { // 向现在正在遍历的子节点分配h个技能点，向已经遍历子节点的分配k-h，看h取多少时ans[root][k]能达到最大// 注意这个递推公式的含义，由题意，激活root技能也需要一个技能点// ans[root][k] 是以root为根节点，向其已经遍历过的子节点分配k个技能点所能达到的power最大值，与我们最后要求的ans[root][k]的含义是不同的// ，后者只能向其子节点分配k-1个技能点// 外层循环一定要从大到小遍历，只有这样在每次计算ans[root][k]时，ans[root][k-h]才能代表“向已经遍历的root的子节点v们分配k-h个技能点所能// 达到的power最大值”, 而不会错误的算入现在正在遍历的这个子节点ans[root][k] = max(ans[root][k], ans[v][h] + ans[root][k-h]);// 这样，当遍历完最后一个子节点时(或者遍历完最后一条出边)，// 就求出了ans[root][k] == 以root为根节点向其所有子节点分配k个技能点，能达到的power最大值}}}// 现在需要求出：以root为根节点，且拥有k个技能点(激活root会消耗一个)时，能达到的power最大值// 这里也必须递减循环，道理比较简单，而且与上面那个外层循环一定要逆序遍历的道理类似for(int i=m;i>=1;i--) ans[root][i] = ans[root][i-1] + power[root];return ;}int main() {cin >> n >> m;for(int i=1;i<=n;i++) {cin >> power[i];}int depend[205] = {0};for(int i=1;i<=n-1;i++) {int u, v; // v技能的开通依赖着ucin >> u >> v;depend[v] = 1;add_edge(u, v);}int root; // 根本技能for(int i=1;i<=n;i++) {if(depend[i] == 0) {root = i;break;}}treedp(root);cout << ans[root][m];}