树形dp
方法1:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6007;
int n;
int w[N],f[N][2];
int B[N],A[N][N];
bool st[N];
void add(int b,int a)
{//B数组记录b的子节点个数A数组记录b子节点分别是什么
int t=B[b];
A[b][t]=a;
B[b]++;
}
void dfs(int u)
{
f[u][1]=w[u];
for(int i=0;i<B[u];i++)
{
int son=A[u][i];
dfs(son);
f[u][1]+=f[son][0];
f[u][0]+=max(f[son][0],f[son][1]);
}
return;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(b,a);
st[a]=true;
}
int root=1;
while(st[root])root++;
dfs(root);
cout<<max(f[root][0],f[root][1])<<endl;
return 0;
}
方法2:
#include<iostream>//没有上司的舞会
#include<cstring>//补充知识邻接表与链表
#include<algorithm>
using namespace std;
const int N=6007;
int n;
int w[N];
int h[N],e[N],ne[N],idx;//h存储邻接表中每个节点的头指针
//通过遍历该链表可以得到与节点i相连的所有节点
bool st[N];//存储该点是否有附着点
int f[N][2];//f(i,0)以i为根的二叉树且不选i的所有集合
//f(i,1)则表示选择i的所有集合的最大值
void add(int b,int a)//将a节点添加到以b节点为起点的链表中并更新指向下一节点的指针ne与头指针h
{//e存储边的终点 e[i]表示第i条边的终点编号
e[idx]=a,ne[idx]=h[b],h[b]=idx++;
}//ne[i]表示第i条边相同起点的下一条索引 遍历该数组得到与同一个起点相连的所有边
void dfs(int u)
{
f[u][1]=w[u];
for(int i=h[u];~i;i=ne[i])//枚举当前节点的所有枝
{//~i 等价于 i!=-1
int j=e[i];
dfs(j);
f[u][0]+=max(f[j][0],f[j][1]);
f[u][1]+=f[j][0];
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(b,a);//b为a的上司则a有附着点
st[a]=true;
}
int root=1;
while(st[root])root++;//寻找整棵树的附着点即根部
dfs(root);
cout<<max(f[root][0],f[root][1])<<endl;
return 0;
}