算法训练 结点选择 蓝桥杯

权值均为不超过1000的正整数。

树形动态规划

建立树

其实就是储存图，有矩阵和链表。我这里用的是链式前向星，储存的图的思路是以每个点为起点，然后用head[i]储存以i为起点的一条边，通过链式结构遍历所有边。具体操作一个是边结构，包含终点，和下一条边的位置，另一个是添加函数，完成储存终点，链式结构，指定新起始边的任务。注意一条边是属于两条边的。

动态规划

类似于最大独立子集问题

子问题 以i为根节点的子树权值和最大值

递归表达式    dp[x][0]+=max2(dp[k][0],dp[k][1]);（0不取x，1取x）                        dp[x][1]+=dp[k][0];

没有重叠子问题，从叶开始只要算一遍。

#include<stdio.h>#define max2(a,b) a>b?a:b#define min2(a,b) a<b?a:b#define Max_ 100010int M=0;int dp[Max_][2];int head[Max_];struct edge{int to;int next;}e[Max_*2];void add(int v, int u){e[M].to=v;e[M].next=head[u];head[u]=M++;e[M].to=u;e[M].next=head[v];head[v]=M++;}void dfs(int x,int v){int i,k;for(i=head[x];i!=-1;i=e[i].next){    k=e[i].to;    if(k==v)continue;    dfs(k,x);    dp[x][0]+=max2(dp[k][0],dp[k][1]);    dp[x][1]+=dp[k][0];}}int main(){int n,i,u,v;scanf("%d",&n);memset(head,-1,sizeof(head));memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){    scanf("%d",&dp[i][1]);}for(i=1;i<=n-1;i++){    scanf("%d%d",&u,&v);    add(u,v);}dfs(1,-1);PRintf("%d",max2(dp[1][1],dp[1][0]));return 0;}