tyvj 创世纪 - 基环树

tyvj 创世纪 - 基环树

codevs :   传送门

Description

　　上帝手中有着N 种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。

每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的

世界元素能够限制它，这样上帝就可以保持对世界的控制。

由于那个著名的有关于上帝能不能制造一块连自己

都不能举起的大石头的二律背反命题，我们知道上帝不是万能的，而且不但不是万能的，他甚至有事情需要找

你帮忙——上帝希望知道他最多可以投放多少种世界元素，但是他只会O(2N) 级别的算法。

虽然上帝拥有无限多

的时间，但是他也是个急性子。

你需要帮助上帝解决这个问题。

题解

把$A[ i ]$ 当作 $f[ i ]$  即父节点

dfs找环 + 断环 + 重连

只需找到环上的任意两个点记录即可

找到了$x， y$ ， 并且$A_x = y$

断环： 让找到的两个点之间的边断开， 从子节点开始$dp$， 算出投放 $x$时的最大值即 $f[x][1]$

重连： 当然不可能真的重连，只需要让 $x$ 不被投放， 并且在处理$y$时， $y$的子节点无需限制它， 因为已经有$x$在限制了

　相当于重连

记得手工栈， 不然会RE

注意一个点组成的环需要一些特判，不然会WA

代码

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #define ll long long

 #define rd read()

 #define rep(i,a,b) for(register int i = (a); i <= (b); ++i)

 #define per(i,a,b) for(register int i = (a); i >= (b); --i)

 #define R register

 using namespace std;

 const int N = 1e6 + 1e3;

 int n, m, fa[N], vis[N];

 int f[N][], pos1, pos2, eg;

 int tot, head[N];

 struct edge {

     int to, nxt;

 }e[N << ];

 int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if( c== '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 void add(int u, int v) {

     e[++tot].to = v;

     e[tot].nxt = head[u];

     head[u] = tot;

 }

 int lev;

 int st_x[N];

 int st_nt[N];

 int st_tmp[N];

 #define x st_x[lev]

 #define nt st_nt[lev]

 #define tmp st_tmp[lev]

 void find_cir(int u) {

     st_x[] = u;

     lev = ;

 start:;

     vis[x] = ;

     nt = fa[x];

     if(vis[nt]) {

         pos1 = x; pos2 = nt;

     }

     else {

         st_x[lev + ] = nt;

         lev++;

         goto start;

     }

 end:;

     if((--lev)) goto end;

 }

 int st_i[N];

 #define i st_i[lev]

 void dp(int u) {

     st_x[] = u;

     lev = ;

 start:;

     tmp = ;

     f[x][] = f[x][] = ;

     vis[x] = ;

     for(i = head[x]; i; i = e[i].nxt) {

         nt = e[i].to;

         if(nt == pos1) continue;

         st_x[lev + ] = nt;

         lev++;

         goto start;

 end:;

         f[x][] = f[x][] + max(f[nt][], f[nt][]);

         tmp += max(f[nt][], f[nt][]);

     }

     for(i = head[x]; i; i = e[i].nxt) {

         nt = e[i].to;

         if(nt == pos1) continue;

         f[x][] = max(f[x][],  + tmp - max(f[nt][], f[nt][]) + f[nt][]);

     }

     if(--lev) goto end;

 }

 void dp2(int u) {

     st_x[] = u;

     lev = ;

 start:;

     tmp = ;

     f[x][] = f[x][] = ;

     for(i = head[x]; i; i = e[i].nxt) {

         nt = e[i].to;

         if(nt == pos1) continue;

         st_x[lev + ] = nt;

         lev++;

         goto start;

 end:;

         f[x][] = f[x][] + max(f[nt][], f[nt][]);

         if(x == pos2 && pos1 != pos2) f[x][] = f[x][] + max(f[nt][], f[nt][]);

         tmp += max(f[nt][], f[nt][]);

     }

     if(x == pos2 && pos1 != pos2) {

         f[x][]++;

         if(--lev) goto end;

     }

     for(i = head[x]; i; i = e[i].nxt) {

         nt = e[i].to;

         f[x][] = max(f[x][],  + tmp - max(f[nt][], f[nt][]) + f[nt][]);

     }

     if(--lev) goto end;

 }

 #undef x

 #undef i

 #undef nt

 #undef tmp

 int work(int x)  {

     int maxn = ;

     find_cir(x);

     dp(pos1);

     maxn = f[pos1][];

     dp2(pos1);

     maxn = max(maxn, f[pos1][]);

     return maxn;

 }

 int main()

 {

     n = rd;

     int ans = ;

     rep(i, , n) fa[i] = rd, add(fa[i], i);

     rep(i, , n) if(!vis[i]) ans += work(i);

     printf("%d\n", ans);

 }