这题目写了我好长时间，但还是几乎(不要在意细节)一遍 A 了喵~
据说有代码奇短的，Orz 思路巧妙的大爷
想我这种 Brute Force 写写的傻 X 真是代码量飞起来了耶，喵~
如果把每个人看成点，每个人要 kill 的人向此人连出一条有向边，那么每个点仅有一条出边和一条入边
经验告诉我们，这就是 环+内向图 的节奏
经验又告诉我，处理这种图要么先暴力搞环，再搞挂在环上的树。要么先搞树，再弄环。
此题显然是后者
环+内向图只需要用 bfs 就可以搞出来了，看到写 tarjan 的真是 Orz
弄出 环 和 树 后，先在树上跑 dp，用 dp[u][0] 表示如果 u 最后被 kill 了，那么以 u 为根子树最少要死几人， dp[u][1] 是 u 存活下来的情况
这是普及组难度的树形 dp 吧喵~
再在环上跑 dp ，我们先破环为链，则有3种情况 (我们令在首的人为 A , 在尾的人为 B)
1. A君 最后活着，那 B君 一定被 kill 了
2. A君 最后被 kill 了，B君 存活了或也被 kill 了
3. A君 存活了下来，B君 也存活了下来，然后 B君 kill A君
三种情况要分类讨论
中间过程的状态转移和以上三种情况类似，无非就是讨论 i 君 和 i+1 君 的是否被 kill 的关系 (妈妈说，某个字打出来是不好的喵~)
被 kill 有两种可能:1.被自己的子树中的某君 kill 了 2.被环上的某君 kill 了
这个 dp 也很好想嘛
似乎除了难写就没有难度了喵？
1 #include <cstdio> 2 #include <cstring> 3 const int size=1000001; 4 const int inf=size; 5 6 namespace IOspace 7 { 8 inline void assign() {freopen("isaac.in", "r", stdin); freopen("isaac.out", "w", stdout);} 9 inline void close() {fclose(stdin); fclose(stdout);} 10 inline int getint() 11 { 12 register int num=0; 13 register char ch; 14 do ch=getchar(); while (ch<'0' || ch>'9'); 15 do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9'); 16 return num; 17 } 18 inline void putint(int num, char ch=' ') 19 { 20 char stack[15]; 21 register int top=0; 22 if (num==0) stack[top=1]='0'; 23 for ( ;num;num/=10) stack[++top]=num%10+'0'; 24 for ( ;top;top--) putchar(stack[top]); 25 if (ch) putchar(ch); 26 } 27 } 28 29 int n; 30 int g[size][2]; 31 int t, a[size]; 32 int f[size], d[size]; 33 int dp[size][2]; 34 bool vis[size], loop[size]; 35 36 struct edge {int point; edge * next;}; 37 edge MEM[size], * PORT=MEM; 38 edge * E[size]; 39 inline edge * newedge(int _point, edge * _next) 40 {edge * ret=PORT++; ret->point=_point; ret->next=_next; return ret;} 41 42 inline int min(int x, int y) {return x<y?x:y;} 43 inline int max(int x, int y) {return x>y?x:y;} 44 inline void add(int & x, int y) {if (x>=inf || y>=inf) x=inf; else x+=y;} 45 inline int search(int); 46 inline int find(int); 47 inline void bfs(int); 48 49 int main() 50 { 51 int ans1=0, ans2=0; 52 53 n=IOspace::getint(); 54 for (int i=1;i<=n;i++) 55 { 56 f[i]=IOspace::getint(), d[f[i]]++; 57 if (f[i]==i) ans2++, vis[i]=1; 58 E[f[i]]=newedge(i, E[f[i]]); 59 } 60 61 for (int i=1;i<=n;i++) if (!d[i]) 62 { 63 vis[i]=1; 64 ans2+=search(i); 65 } 66 for (int i=1;i<=n;i++) if (!vis[i]) 67 { 68 vis[i]=1; 69 ans2+=search(i); 70 } 71 72 memset(vis, 0, sizeof(vis)); 73 for (int i=1;i<=n;i++) if (!vis[i]) 74 { 75 vis[i]=1; 76 ans1+=find(i); 77 } 78 79 IOspace::putint(ans1, ' '); IOspace::putint(ans2); 80 81 return 0; 82 } 83 inline int search(int x) 84 { 85 int ret=0; 86 for (x=f[x];!vis[x];x=f[x]) vis[x]=1, ret++; 87 return ret; 88 } 89 inline void bfs(int x) 90 { 91 static int l, r, q[size]; 92 93 l=r=0; 94 for (q[r++]=x;l<r; ) 95 { 96 int u=q[l++]; 97 for (edge * i=E[u];i;i=i->next) 98 if (!loop[i->point]) 99 { 100 vis[i->point]=1; 101 q[r++]=i->point; 102 } 103 } 104 105 for (int i=r-1;i>=0;i--) 106 if (E[q[i]]==NULL) dp[q[i]][0]=inf; 107 else if (E[q[i]]->next==NULL && loop[E[q[i]]->point]) dp[q[i]][0]=((E[q[i]]->point)==q[i])?1:inf; 108 else 109 { 110 for (edge * j=E[q[i]];j;j=j->next) 111 if (!loop[j->point]) 112 add(dp[q[i]][1], dp[j->point][0]); 113 for (edge * j=E[q[i]];j;j=j->next) 114 if (!loop[j->point]) 115 add(dp[q[i]][0], min(dp[j->point][0], dp[j->point][1])); 116 add(dp[q[i]][0], 1); 117 } 118 } 119 inline int find(int x) 120 { 121 int ret=0; 122 123 vis[x]=1; 124 for (x=f[x];!vis[x];x=f[x]) vis[x]=1; 125 for (t=0;!loop[x];x=f[x]) loop[a[t++]=x]=1; 126 for (int i=0;i<t;i++) bfs(a[i]); 127 if (t==1) return dp[a[0]][0]; 128 g[0][1]=dp[a[0]][1]; g[0][0]=inf; 129 for (int i=1;i<t;i++) 130 { 131 g[i][0]=min(g[i-1][0], g[i-1][1]); 132 add(g[i][0], min(dp[a[i]][0], dp[a[i]][1]+1)); 133 g[i][1]=g[i-1][0]; 134 add(g[i][1], dp[a[i]][1]); 135 } 136 ret=g[t-1][0]; 137 138 g[0][0]=dp[a[0]][0]; g[0][1]=inf; 139 for (int i=1;i<t;i++) 140 { 141 g[i][0]=min(g[i-1][0], g[i-1][1]); 142 add(g[i][0], min(dp[a[i]][0], dp[a[i]][1]+1)); 143 g[i][1]=g[i-1][0]; 144 add(g[i][1], dp[a[i]][1]); 145 } 146 ret=min(ret, min(g[t-1][0], g[t-1][1])); 147 148 g[0][0]=dp[a[0]][1]+1; g[0][1]=inf; 149 for (int i=1;i<t;i++) 150 { 151 g[i][0]=min(g[i-1][0], g[i-1][1]); 152 add(g[i][0], min(dp[a[i]][0], dp[a[i]][1]+1)); 153 g[i][1]=g[i-1][0]; 154 add(g[i][1], dp[a[i]][1]); 155 } 156 ret=min(ret, g[t-1][1]); 157 158 return ret; 159 }