[题目|树形dp]P1352 没有上司的舞会
题目描述
某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式：
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0 0
输出格式：
输出最大的快乐指数。
输入样例#1：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
输出样例#1：
5
思想：
纪念一下第一道树形dp题，存图用链式前向星生疏了，并且加深了一些理解。
理解1：next的定义记错了，每当一个起点遍历结束以后，最终点的next总是指向0，（而不是只有一个点指向0）这使得按父子关系如dfs的遍历方式成为可能。
理解2：cnt从1还是从0开始取决于题目点编号是从1开始还是0。（因为add函数里加head[from]时的from是读取自起始点，可能取不到0）
理解3：此题是典型的无根树，需要定义is_son数组并且通过遍历来找根节点。
理解4：树形dp的特点一般是借助于dfs，其大致格式为每次遍历之前首先初始化当前点，之后取edge[i].to中的点进行递归，之后是状态转移方程。本题是二维，第二个维度有两个状态，具体题目具体定义。
题解：
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<iostream>
#include<map>
#define M 6005
using namespace std;
const int inf=0x7f7f7f7f;
int r[M];
struct edge1{
int next;
int to;
int val;
}edge[M];
int head[M];
bool is_son[M];
int dp[M][2];
int cnt;
void add(int from,int to,int val)
{
edge[cnt].to=to;
edge[cnt].val=val;
edge[cnt].next=head[from];
head[from]=cnt++;
}
int Dp(int rec)
{
dp[rec][0]=0;
dp[rec][1]=r[rec];
for(int i=head[rec];i!=0;i=edge[i].next)
{
int g=edge[i].to;
Dp(g);
dp[rec][0]+=max(dp[g][1],dp[g][0]);
dp[rec][1]+=dp[g][0];
}
}
int main()
{
ios::sync_with_stdio(false);
int n,l,k;
int rec;
cin>>n;
cnt=1;
for(int i=1;i<=n;i++)
{
cin>>r[i];
}
memset(edge,0,sizeof(edge));
memset(head,0,sizeof(head));
memset(dp,0,sizeof(dp));
memset(is_son,false,sizeof(is_son));
for(int i=1;i<=n-1;i++)
{
cin>>l>>k; //k(boss) -> l(staff)
// add(l,k,1); //此处是一开始想错了
add(k,l,1);
is_son[l]=true;
}
cin>>l>>k;
for(int i=1;i<=n;i++)
{
if(!is_son[i])
{
rec=i;
break;
}
}
Dp(rec);
cout<<max(dp[rec][0],dp[rec][1])<<endl;
return 0;
}