蓝桥杯2015年第六届真题-生命之树-题解（C++代码）

解题思路:
树形dp

f[i][0]表示不选i点的最大子树权值

f[i][1]表示选i点的最大子树权值

f[i][0]=max(f[j][0],f[j][1]) {j是i的子节点}

f[i][1]=val[i]+SUM(max(0,f[j][1])) {j含义与上面一致}
注意事项:

参考代码:

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll; 
const int N=1e5+10; 
int h[N],e[2*N],ne[2*N],idx;
ll f[N][2];
int val[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa){
f[u][0]=0,f[u][1]=val[u];
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==fa)continue;
dfs(j,u);
f[u][0]=max(f[u][0],max(f[j][0],f[j][1]));
f[u][1]+=max(0ll,f[j][1]);
}
}
int main()
{
int n;
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;++i)cin>>val[i];
for(int i=1;i<n;++i){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1,0);
cout<<max(f[1][0],f[1][1])<<endl;
}