[洛谷 1352,poj 2342]没有上司的舞会

题目链接

https://www.luogu.org/problem/P1352

题解

我们定义状态 \(f(i,0/1)\) 代表以 \(i\) 为根的子树的最优解（第二维的值为 0 代表 \(i\) 不参加舞会的情况，1 代表 \(i\) 参加舞会的情况）

我们可以得到下面两个状态转移方程（其中 \(x\) 为 \(i\) 的子节点）：

• \(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\)（上司不参加舞会时，下属可以参加，也可以不参加）
• \(f(i,1) = \sum f(x,0) + a_i\)（上司参加舞会时，下属都不会参加）

我们可以通过 DFS，在返回上一层时更新当前节点的最优解。

#include <cstdio>
#include <algorithm>
using namespace std;
struct edge
{
 int v,next;
}e[6005];
int head[6005],n,cnt,f[6005][2],ans,is_h[6005],vis[6005];
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void calc(int k)
{
 vis[k]=1;
 for(int i=head[k];i;i=e[i].next)
 {
  if(vis[e[i].v])continue;
  calc(e[i].v);
  f[k][1]+=f[e[i].v][0];
  f[k][0]+=max(f[e[i].v][0],f[e[i].v][1]);
 }
 return;
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&f[i][1]);
 for(int i=1;i<n;i++)
 {
  int l,k;
  scanf("%d%d",&l,&k);
  is_h[l]=1;
  addedge(k,l);
 }
 for(int i=1;i<=n;i++)
  if(!is_h[i])
  {
   calc(i);
   printf("%d",max(f[i][1],f[i][0]));
   return 0;
  }
}