没有上司的晚会

最大独立子集 没有上司的晚会

题目描述

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。 输入格式 第一行一个整数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 样例输出 5

分析

首先拿到这个题，就会先把根给求出来 然后，分析题意，其实，如果选fa，那，son一定不行，但不选fa，son可选可不选，这时，我们就会想到，打dfs,或dp，但又想想，dfsO(2^n),肯定不好，dp，虽然好像可以，但，好像没有阶段，于是，就要用树形DP dp[x][0] =max(dp[s][0],dp[s][1]) dp[x][1] = H[x] + dp[son][0](son∈Son(x) 比如dp[i][1]表示以i号节点为子树的根，当它参会时整棵子树的快乐指数和；dp[i][0]表示以i号节点为子树的根，当它不参会时整棵子树的快乐指数和 很明显，这就是由叶节点，一点点的传到根

#include<bits/stdc++.h> using namespace std; int n; int a[100050]; int x,y; vector<int>g[100005]; int dp[10005][2]; int fa[100005]; int root; void dfs(int x) { dp[x][1]=a[x]; dp[x][0]=0; for(int i=0;i<g[x].size();i++) { int v=g[x][i]; dfs(v); dp[x][1]+=dp[v][0]; dp[x][0]+=max(dp[v][0],dp[v][1]); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n-1;i++) { scanf("%d %d",&x,&y); g[y].push_back(x); fa[x]=1; } for(int i=1;i<=n;i++) { if(!fa[i]) { root=i; break; } } dfs(root); printf("%d",max(dp[root][1],dp[root][0])); }