P1352 没有上司的舞会
斯德哥尔摩
2018-10-24 19:37:31
[P1352 没有上司的舞会](https://www.luogu.org/problemnew/show/P1352)
头一次写树形$DP$的板子题，竟然$1A$！
好开森啊！！！
首先，我们知道这是棵树（废话。。。）。
然后对于每个选择有后效性，我们自然想到只考虑上司对下属的限制。
然后开始$DP$。
设$dp[i][0/1]$表示对于第$i$个节点的子树，选与不选$i$的能获得的最大价值。
由于有负值，于是状态转移方程长这个样：
$$dp[i][0]+=\max\left\{\begin{array}{}0\\dp[j][0]\\dp[j][1]\end{array}\right.$$
$$dp[i][1]+=\max\left\{\begin{array}{}0\\dp[j][0]\end{array}\right.$$
其中$j$为$i$的儿子。
然后一遍$DFS$即可。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 6010
using namespace std;
int n,root,ans,c=1;
int val[MAXN],head[MAXN],deep[MAXN],fa[MAXN],dp[MAXN][2];
struct Edge{
int next,to;
}a[MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add_edge(int x,int y){
a[c].to=y;a[c].next=head[x];head[x]=c++;
a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int rt){
dp[rt][0]=0;
dp[rt][1]=val[rt];
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(deep[will])continue;
deep[will]=deep[rt]+1;
dfs(will);
dp[rt][0]+=max(0,max(dp[will][0],dp[will][1]));
dp[rt][1]+=max(0,dp[will][0]);
}
}
void work(){
ans=max(dp[root][0],dp[root][1]);
printf("%d\n",ans);
}
void init(){
int x,y;
n=read();
for(int i=1;i<=n;i++)val[i]=read();
for(int i=1;i<n;i++){
x=read();y=read();
fa[x]=y;
add_edge(x,y);
}
for(int i=1;i<=n;i++)if(!fa[i]){root=i;break;}
deep[root]=1;
dfs(root);
}
int main(){
init();
work();
return 0;
}
```