题解：P11501 [ROIR 2019] 探险队(Day 2)

前言：这道题 dp 做法找环的部分还没有用拓扑做的，补充一下。

这道题其实很像“上司的舞会”，就是求树上最大独立集。

这里我们把每个人向他讨厌的那个人连边（发现所有点出度均为 $1$，所以这是一个基环树）然后求树上相邻两个结点不能同时选择时，最多能选多少个点。

如果是在普通的树上，设 $f[i][1/0]$ 表示结点 $i$ 选或不选的最大价值，dp 即可。

基环树相当于套了一个环，考虑把环上的每一个点都当作根，跑一遍它们子树的最大点独立集（注意不能走到环上的点），然后再用“给一个环，相邻的两个元素不选，求选得的最大总和”的 dp 模板，对“基环”上的点再跑一遍 dp 把答案整合起来即可。

因为 DAG 图具有良好的 dp 结构，找环可以用拓扑排序，先把普通的点都 dp 了，拓扑结束后入度依然不为 $0$ 的点就是环上的点。

一些实现细节见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 7;
const ll inf = 1e18;int a[maxn], ind[maxn]; // ind记录入度
ll f[maxn][2]; // f[u][1/0]表示以选/不选u，其子树能得到的最大点独立集大小
bool vis[maxn]; // 记录每个点所在的连通块是否访问过int main(){ios::sync_with_stdio(false); cin.tie(0);int n;cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];if(a[i] != -1){ind[a[i]] ++;}}queue<int> q;for(int i = 1; i <= n; i ++){if(ind[i] == 0){q.push(i);}f[i][1] = 1; // 初始化dp}ll ans = 0;while(!q.empty()){int u = q.front(); q.pop();int v = a[u];if(v == -1){ans += max(f[u][0], f[u][1]); // 说明这个根节点不在环上，那么直接统计答案就好了}else{f[v][0] += max(f[u][0], f[u][1]); // 正常的树上最大独立集dpf[v][1] += f[u][0];ind[v] --;if(ind[v] == 0){q.push(v);}}}// 遍历剩下的入度不为0的结点（说明在环上）for(int i = 1; i <= n; i ++){if(ind[i] >= 1 && !vis[i]){vector<int> ring;ring.push_back(0); // 让下标从1开始int u = i;while(!vis[u]){ // 从一个点一直走，直到回到自己，就说明跑完了一整个环vis[u] = true;ring.push_back(u);u = a[u];}int len = ring.size() - 1;vector<vector<ll>> g(len + 1, {0, 0}); // g[i][1/0]表示结点i选/不选的最大答案（i在环上）// 首先钦定最后一个不选，则第一个选不选都行g[1][0] = f[ring[1]][0], g[1][1] = f[ring[1]][1];for(int j = 2; j <= len; j ++){g[j][0] = max(g[j - 1][0], g[j - 1][1]) + f[ring[j]][0];g[j][1] = g[j - 1][0] + f[ring[j]][1];}ll res1 = g[len][0];// 然后钦定第一个不选，则最后一个选不选都行g[1][0] = f[ring[1]][0], g[1][1] = -inf; // 初始化第一个选的收益为负无穷，相当于强制不选第一个for(int j = 2; j <= len; j ++){g[j][0] = max(g[j - 1][0], g[j - 1][1]) + f[ring[j]][0];g[j][1] = g[j - 1][0] + f[ring[j]][1];}ll res2 = max(g[len][0], g[len][1]);ans += max(res1, res2);}}cout << ans << '\n';return 0;
}