一道基环树+树形(DP)
原题链接
显然输入的是内向基环树森林，且我们可以单独考虑每一棵基环树。
既然是基环树，自然先(dfs)找环，然后随便找环上的一点(r)，将其与(A[r])的边断开，建反边，这时就会形成一棵以(r)为根的树，且每个点的子节点都是能限制它的元素。
于是我们可以在这棵树上跑树形(DP)。
定义(f[x][0])表示不投放元素(x)的时候，以(x)为根的子树中能投放元素的最大值；(f[x][1])表示投放元素(x)的时候，以(x)为根的子树中能投放元素的最大值。
- 不投放(x)时，它的子节点可以投放，也可以不投放。
(qquadqquad f[x][0]=sumlimits_{A[y]=x}max{f[y][0],f[y][1]})
- 投放(x)时，至少有一个子节点是不投放的，以限制(x)。
(qquadqquad f[x][1]=maxlimits_{A[y]=x}{f[y][0]+sumlimits_{A[z]=y,z e y}max{f[z][0],f[z][1]}})
(DP)完成后，用(max{f[r][0],f[r][1]})来更新答案。
然后考虑断边的影响，即导致(r)无法限制(A[r])，所以我们强制令(r)限制(A[r])，然后再进行一遍树形(DP)。当(DP)中计算(f[A[r]][1])时，其子节点可以投放，也可以不投放，因为(A[r])已经被(r)限制，所以不需要再有子节点限制它，而对于其它点的转移方程依旧不变。最后再用(f[r][0])去更新答案，因为我们强制让(r)去限制(A[r])，所以(r)不能被投放。
注意这题使用普通的递归会(MLE)，所以要打手工栈。
#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
int fi[N], di[N << 1], ne[N << 1], a[N], f[N][2], st_x[N], st_i[N], st_y[N], st_s[N], cb, l;
bool v[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c<'0' || c>'9'; c = getchar())
p |= c == '-';
for (; c >= '0'&&c <= '9'; c = getchar())
x = x * 10 + (c - '0');
return p ? -x : x;
}
inline void add(int x, int y)
{
di[++l] = y;
ne[l] = fi[x];
fi[x] = y;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
void dfs(int x)
{
int y;
v[x] = 1;
for (y = a[x]; y; y = a[y])
{
if (v[y])
{
cb = y;
return;
}
v[y] = 1;
}
}
void dp(int x)
{
int k = 1;
st_x[1] = x;
start:
st_s[k] = 0;
v[st_x[k]] = 1;
f[st_x[k]][0] = f[st_x[k]][1] = 0;
for (st_i[k] = fi[st_x[k]]; st_i[k]; st_i[k] = ne[st_i[k]])
{
st_y[k] = di[st_i[k]];
if (st_y[k] ^ cb)
{
st_x[k + 1] = st_y[k];
k++;
goto start;
end:
st_s[k] += maxn(f[st_y[k]][0], f[st_y[k]][1]);
}
}
f[st_x[k]][0] = st_s[k];
for (st_i[k] = fi[st_x[k]]; st_i[k]; st_i[k] = ne[st_i[k]])
{
st_y[k] = di[st_i[k]];
if (st_y[k] ^ cb)
f[st_x[k]][1] = maxn(f[st_x[k]][1], 1 + st_s[k] - maxn(f[st_y[k]][0], f[st_y[k]][1]) + f[st_y[k]][0]);
}
if (--k)
goto end;
}
void dp_2(int x)
{
int k = 1;
st_x[1] = x;
start:
st_s[k] = 0;
f[st_x[k]][0] = f[st_x[k]][1] = 0;
for (st_i[k] = fi[st_x[k]]; st_i[k]; st_i[k] = ne[st_i[k]])
{
st_y[k] = di[st_i[k]];
if (st_y[k] ^ cb)
{
st_x[k + 1] = st_y[k];
k++;
goto start;
end:
st_s[k] += maxn(f[st_y[k]][0], f[st_y[k]][1]);
}
}
f[st_x[k]][0] = st_s[k];
if (!(st_x[k] ^ a[cb]))
{
f[st_x[k]][1] = st_s[k] + 1;
if (--k)
goto end;
return;
}
for (st_i[k] = fi[st_x[k]]; st_i[k]; st_i[k] = ne[st_i[k]])
{
st_y[k] = di[st_i[k]];
if (st_y[k] ^ cb)
f[st_x[k]][1] = maxn(f[st_x[k]][1], 1 + st_s[k] - maxn(f[st_y[k]][0], f[st_y[k]][1]) + f[st_y[k]][0]);
}
if (--k)
goto end;
}
int main()
{
int i, n, ma, s = 0;
n = re();
for (i = 1; i <= n; i++)
{
a[i] = re();
add(a[i], i);
}
for (i = 1; i <= n; i++)
if (!v[i])
{
ma = 0;
dfs(i);
dp(cb);
ma = maxn(f[cb][0], f[cb][1]);
dp_2(cb);
ma = maxn(ma, f[cb][0]);
s += ma;
}
printf("%d", s);
return 0;
}