题目描述
给你一个 \(n\) 个点 \(n\) 条边的有向图，若选了当前节点，那么当前节点的儿子节点至少有一个不能选。求最多能选多少个点。
具体思路
显然是一棵基环树，因此考虑基环树 dp。
我们先不管环的条件，先考虑朴素的树形 dp。
设 \(f_{x,0}\) 表示 \(x\) 节点不选，最多可以选多少个点，\(f_{x,1}\) 表示 \(x\) 节点选，最多可以选多少个点。
如果 \(x\) 不选的话，那么 \(x\) 的儿子 \(y\) 选或不选都没关系，有：
\[f_{x,0}=\max \limits_{y \in son(x)} \{ {f_{y,0},f_{y,1}} \} \]如果 \(x\) 选的话，那么 \(x\) 的儿子里面就一定要有一个点不选，我们枚举这个不选的点，有：
\[f_{x,1}=\max \limits_{y \in son(x)} \{ {f_{y,0}+ \max \limits_{z \in son(x),z \ne y} \{ {f_{z,0},f_{z,1}} \}} \} \]显然这个状态转移方程是 \(O(n^2)\) 的，考虑优化。
我们发现 \(\max \limits_{z \in son(x),z \ne y} \{ {f_{z,0},f_{z,1}} \}\) 和 \(f_{x,0}\) 的转移很像，因此考虑用 \(f_{x,0}\) 来表示 \(f_{x,1}\)。
有：
\[f_{x,1}=f_{x,0}+1+\max \limits_{y \in son(x)} \{ {f_{y,0}-\max(f_{y,0},f_{y,1})} \} \]我们来理解一下这个式子。
首先，加一是因为你当前选了 \(x\) 这个点，因此贡献要加一。
其次，加上 \(f_{y,0}\) 是因为你 \(y\) 这个点不选，因此要加上它不选的贡献。
然后，我们发现 \(f_{x,0}\) 里面计算了一遍 \(y\) 的贡献，因此我们要将它减去。
最后，我们设的 \(f_{x,1}\) 表示的是最多可以放多少个点，因此要对每个 \(y\) 都取一遍最大值。
现在问题就转换成了如果树上有环，应该如何计算这个环对动态规划的影响。
如图所示，\(x\) 和 \(y\) 分别是环的两个端点，考虑断边 \(edge(x,y)\)。
-
若 \(edge(x,y)\) 没有影响
-
若 \(x\) 不选，那么 \(y\) 选不选都没关系。
-
若 \(x\) 选，但 \(x\) 有除 \(y\) 以外的儿子，那么我们把 \(edge(x,y)\) 断了，那么我们 dp 的时候枚举不选的点就是 \(x\) 的其他儿子，那么此时 \(y\) 选不选都没关系。
-
-
若 \(edge(x,y)\) 有影响
- 显然只有一种情况，\(x\) 选，并且 \(y\) 强制不选，那么此时我们的 dp 就要略加修改。
因为我们强制 \(y\) 不选，因此在 dp 的时候我们不用在枚举哪个点不选了，有：
\[f_{x,1}=f_{x,0}+1 \]Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int inf=0x3f3f3f3f;
struct edge{int x,y,pre;}a[N];
int last[N],alen;
void ins(int x,int y){
a[++alen]=edge{x,y,last[x]};
last[x]=alen;
}
int fa[N],f[N][2],v[N],rt,bk;
void treedp(int x){
f[x][0]=f[x][1]=0,v[x]=1;
int res=-inf;
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(y==rt)continue;
treedp(y);
f[x][0]+=max(f[y][0],f[y][1]);
res=max(res,f[y][0]-max(f[y][0],f[y][1]));
}
f[x][1]=f[x][0]+res+1;
if(x==fa[rt]&&bk){
f[x][1]=f[x][0]+1;
}
}
int main(){
int n;scanf("%d",&n);
alen=1;memset(last,0,sizeof(last));
for(int i=1;i<=n;i++){
scanf("%d",&fa[i]);
ins(fa[i],i);
}
int ans=0;
for(int i=1;i<=n;i++){
if(v[i])continue;
rt=i;
while(!v[fa[rt]]){
v[rt]=1;
rt=fa[rt];
}
bk=0;treedp(rt);
int res=max(f[rt][0],f[rt][1]);
bk=1;treedp(rt);
res=max(res,f[rt][0]);
ans+=res;
}
printf("%d",ans);
return 0;
}