题解 P1352 【没有上司的舞会】

这道题作为一道十分经典的树形dp，它显然是像我们这样的新手拿来学习和试手的一道好题。 首先我们们分析一下这道题，对于每一个人，它所做的决定对上司和下属都有影响，我们可以只看一方，也就是上司对下属的影响，因为这样的影响是相互的。 状态如果为f[i]表示第i个人的位置能获得最大的幸福行吗？ 由于我们的选择具有后效性，因为你去或不去对下属有影响，那显然不行。遇到这种情况我们该怎么办？ #加一维 由于后效性实质上是我们对于状态的性质不够清楚，所以我们再加一维以实现就算你加还是不加我们都可以记录下来。所以状态其实是很好想的。想出状态后，容易推出方程为 dp[i][0]=sum(max(dp[son][1],dp[son][0])); 显然，你不去，那下属就可以想去就去。 dp[i][1]=sum(dp[son][0])+happy[i]; 显然你去了那下属就一定不能去。 由此我们就可以愉快的DFS了。 #但是 如果我们的人数相当多且是一条链的时候就容易造成爆栈，那这我们有如何解决呢?方法有三 1. 开一个数组手动实现栈。 2. bfs后用for循环 3. 拓扑排序 第一个想必大家都会写，而且其与dfs相似，所以不再赘述。 那为啥会讲后两种呢？ 因为有时候dfs并不好写，所以我们会把它转化为bfs+for或者拓扑，大家可以看一下，dfs和这两种写法的推导有的是不一样的。特别是和这题的拓扑写法，可以仔细看一下。 那么首先说下bfs 我们很容易发现树形dp它为什么一般会是dfs形式？因为树形dp的状态大多是一颗颗子树，它传递状态过程一般都是先求出最下层再往上更新。所以对于每一个点，我们在求解它的值的过程中，需要求出它每一个子节点的解。那有什么方法我们可以用数组和for循环实现这样的求解呢？没错，就是bfs过程中的**队列**。由于队列中的点都是先入的父亲节点后入的子节点，所以我们求解的时候只要把循环顺序反过来就可以了。以下代码 ```cpp #include<bits/stdc++.h> using namespace std; int t=0,que[6005],happy[6005],fa[6005]; vector<int>son[6007]; queue<int> q; bool vis[6005]; int dp[6005][2]; void bfs(int s) { q.push(s); vis[s]=1; que[++t]=s; while(!q.empty()) { int u=q.front(); q.pop(); int x=son[u].size(); for(int i=0;i<x;i++) { if(!vis[son[u][i]]) { vis[son[u][i]]=1; q.push(son[u][i]); que[++t]=son[u][i]; } } } return ; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { fa[i]=i; scanf("%d",&happy[i]); } int a,b; while(scanf("%d %d",&a,&b)) { if(a==0&&b==0) break; fa[a]=b; son[b].push_back(a); } int s=n; while(s!=fa[s]) s=fa[s]; bfs(s); for(int i=t;i>0;i--) { int u=que[i]; int x=son[u].size(); for(int j=0;j<x;j++) { int v=son[u][j]; dp[u][0]+=max(dp[v][0],dp[v][1]); dp[u][1]=max(dp[u][1],dp[u][1]+dp[v][0]); } dp[u][1]+=happy[u]; } printf("%d",max(dp[s][0],dp[s][1])); return 0; } ``` 接下来我们谈谈拓扑排序做法。 先来回顾一下，拓扑排序的时候我们其实是从根到子节点，那么如何实现从子节点返回根节点的求解过程呢？**反向连边存入度**。没错，反向，就可以轻易实现这样的求解。可以自己手动模拟一下。然后对于这样的求解，我们可以在边求拓扑排序边更新答案。 至于为啥其实很好想的，可以自己推推（其实我懒了） ```cpp #include<bits/stdc++.h> using namespace std; int happy[6005]; int ru[6005]; int fa[6005]; int dp[6005][2]; int main() { int n; scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d",&happy[i]); } int a,b; while(scanf("%d %d",&a,&b)) { if(a == 0&&b == 0) break; ru[b]++; fa[a] = b; } queue<int>q; for(int i = 1;i <= n;i++) { if(ru[i] == 0) q.push(i); } int maxn = 0; while(!q.empty()) { int u = q.front(); q.pop(); dp[u][1] += happy[u]; maxn = max(dp[u][1],maxn); maxn = max(dp[u][0],maxn); ru[fa[u]] --; if(ru[fa[u]] == 0) q.push(fa[u]); dp[fa[u]][0] = max(dp[fa[u]][0] + dp[u][0],dp[fa[u]][0] + dp[u][1]); dp[fa[u]][1] += dp[u][0] >= 0 ? dp[u][0] : 0; } printf("%d",maxn); } ``` 希望这篇题解能对大家有点帮助 还有这是我的博客来看看也好，就是luogu的。 希望顶顶，我也会写一些其他树形dp的题解，谢谢大家啦 #[博客](https://www.luogu.org/blog/mak2333/)