没有上司的舞会
Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。
输出最大的快乐指数。
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
5
各个测试点1s
一个节点的父亲就是它的直接上司，没有职员愿和直接上司一起与会 就是要求节点和父节点不能同时选择，注意题目输入边的关系时输入u、v表示的是v是u的父亲。题目没有给根节点，所以我这里用边表来储存树，边读入边标记有父亲的点flag值为1，读入结束后再扫描一遍flag数组，flag值为0的节点就是根节点了，因为它没有父亲。接着我们就直接写一个函数dp根节点。
那么这个dp的递归函数该怎么写呢？我们先来想办法推出状态转移方程。
对于每个节点，我们都有取和不取两个操作。f[i][0]和f[i][1]分别表示i节点取和不取得到的最大值。虽然题目里给定点的权值范围是(-128<=Ri<=127)，但是我们要首先大胆地肯定一点：f[i][0]不可能小于0，f[i][1]不可能小于i点的权值也就是dis[i]。为什么？因为我们要求最大的价值，而如果当下面的节点权值都为负数会出现“越取越小”的情形时，我们就干脆一个节点都不取，这样子取得的价值就直接为0，f[i][1]不可能小于i点的权值也是同理：取了i点的权值后，若i的儿子权值都是负数，越取越小，则干脆不取，这样f[i][1]就会变成dis[i]，也不可能小于dis[i]。所以f[i][0]不可能小于0，f[i][1]不可能小于i点的权值也就是dis[i]。
注：edge[j].to存储的是i节点的儿子节点，详情可以看我的代码中边表的实现；0表示不取，1表示取。
因为这是树形dp，我们当然是从父亲递归到每一个儿子啦。对于每个节点，我们都有取和不取两个操作。如果i节点取的话，i节点的儿子节点就一定不能取，所以f[i][1]+=f[edge[j].to][0]。如果有人问我为什么f[i][1]是“+=”f[edge[j].to][0]而不是“=”，那我只能说：人家又不是只有一个儿子，你如果把i点取的值直接等于儿子不取的最大价值的话，那简直就是事故现场，你可以想想如果这么做你为什么有存储f[i][1]的必要，因为f[i][1]的值在f[edge[j].to][0]就存储了。而如果i节点不取的话，i节点的儿子就有了两种选择：取和不取。而对于这两种选择，我们当然选择更大的价值啦。所以f[i][0]+=max(f[edge[j].to][0],f[edge[j].to][1]);。
然后我再拿出一段代码分析一下，也就是核心代码：dp的函数：
void dp(int i)
{
for (int j=head[i]; j; j=edge[j].next) {//遍历每一条以i为起点的边j。
dp(edge[j].to);//先递归一下待会需要用到的儿子节点，你可以理解成准备dp需要用的东西。
f[i][1]+=f[edge[j].to][0];//这里不需要用到max函数，我前面已经解释过了最大值不可能是负数，所以不需要。这里是取i点的最大价值。
f[i][0]+=max(f[edge[j].to][0],f[edge[j].to][1]);//这是不取i点的最大价值。
}
f[i][1]+=dis[i];//1表示当前点要取，既然取了这个点，就要加上这个点的权值。
return;
}
还是不懂的同学可以自己拿笔和纸模拟一下，其实我的核心代码很短的。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
int read()
{
int f=,x=; char c=getchar();
while (c>''||c<'') {if (c=='-') f=-; c=getchar();}
while (c>='' && c<='') {x=x*+c-''; c=getchar();}
return x*f;
}
int num_edge,head[],f[][],n,dis[],u,v,gen;
long long MAX=;
bool flag[];
struct Edge
{
int next;
int to;
}edge[];
void Add_edge(int from,int to)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
void dp(int i)
{
for (int j=head[i]; j; j=edge[j].next) {
dp(edge[j].to);
f[i][]+=f[edge[j].to][];
f[i][]+=max(f[edge[j].to][],f[edge[j].to][]);
}
f[i][]+=dis[i];
return;
}
int main()
{
n=read();
for (int i=; i<=n; i++) dis[i]=read();
for (int i=; i<=n-;i++) {
u=read(); v=read();
Add_edge(v,u);
flag[u]=;
}
u=read();
v=read();
for (int i=; i<=n; i++)
if (flag[i]==) {
gen=i;
break;
}
dp(gen);
if (f[gen][]>f[gen][]) printf("%d\n",f[gen][]);
else printf("%d\n",f[gen][]);
return ;
}
没有上司的舞会
有问题可以直接在评论里面提问，有需要转载的请得到我的允许，否则按侵权处理。
Elena loves NiroBC forever!