P1352 没有上司的舞会【洛谷算法习题】

P1352 没有上司的舞会

网页链接

P1352 没有上司的舞会

题目描述

某大学有

n

n

n 个职员，编号为

1

…

n

1\\ldots n

1…n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数

r

i

r_i

ri​，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数

n

n

n。

第

2

2

2 到第

(

n

+

1

)

(n + 1)

(n+1) 行，每行一个整数，第

(

i

+

1

)

(i+1)

(i+1) 行的整数表示

i

i

i 号职员的快乐指数

r

i

r_i

ri​。

第

(

n

+

2

)

(n + 2)

(n+2) 到第

2

n

2n

2n 行，每行输入一对整数

l

,

k

l, k

l,k，代表

k

k

k 是

l

l

l 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

输入输出样例 #1

输入 #1

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出 #1

5

说明/提示

数据规模与约定

对于

100

%

100\\%

100% 的数据，保证

1

≤

n

≤

6

×

10

3

1\\leq n \\leq 6 \\times 10^3

1≤n≤6×103，

−

128

≤

r

i

≤

127

-128 \\leq r_i\\leq 127

−128≤ri​≤127，

1

≤

l

,

k

≤

n

1 \\leq l, k \\leq n

1≤l,k≤n，且给出的关系一定是一棵树。

解题思路

本题是经典的**树形动态规划（树的最大独立集）**入门题，在树形结构上求解“相邻节点不可同时选取”的最大权值和问题。 职员的从属关系构成一棵有根树，定义二维DP状态：f[x][0] 表示节点 x 不参加舞会时，以 x 为根的子树能获得的最大快乐值；f[x][1] 表示节点 x 参加舞会时的对应最大值。 状态转移严格遵循“直属上司与职员不能同时参加”的约束：

• 若当前节点参加舞会，则所有直接子节点均不能参加，累加所有子节点的“不参加”状态值，再加上自身快乐值。
• 若当前节点不参加舞会，则每个子节点可自由选择参加或不参加，累加每个子节点两种状态的最大值。 采用后序深度优先遍历实现：先递归处理所有子节点，再回溯更新父节点状态。最终取根节点两个状态的最大值即为答案，算法时间复杂度 $O(n)$

总结

核心逻辑：基于树结构的双状态动态规划，通过“选/不选”两个状态自底向上递推，求解无相邻节点的最大权值和。 关键操作：邻接表存储树形结构、查找根节点、后序DFS完成状态转移、取根节点双状态最大值。 效率保障：每个节点仅遍历一次，线性时间复杂度，无冗余运算，轻松处理千级节点规模。

代码简要说明

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

#define MAXN 6005
ll h[MAXN];
ll v[MAXN];
vector<ll> son[MAXN];
ll f[MAXN][2];

void dp(ll x)
{
f[x][0]=0;
f[x][1]=h[x];
for(ll i=0;i<(ll)son[x].size();i++)
{
ll y=son[x][i];
dp(y);
f[x][0]+=max(f[y][0],f[y][1]);
f[x][1]+=f[y][0];
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll n;
cin>>n;
for(ll i=1;i<=n;i++) cin>>h[i];
for(ll i=1;i<=n–1;i++)
{
ll x,y;
cin>>x>>y;
son[y].push_back(x);
v[x]=1;
}
ll root;
for(ll i=1;i<=n;i++) if(!v[i]) {root=i; break;}
dp(root);
cout<<max(f[root][0],f[root][1])<<endl;
return 0;
}