这种题好难做啊…

求最大值,是可以构造方案使得所有都没被挡路的:

对于每个子树(内向树的子树),我们可以让每个父亲选择一个大儿子,把这条边染黑。这样得到了一个树的链剖分,每条链一定以叶子结尾。对于每条链,我们从上到下,把儿子作为父亲的真理捍卫者。然后每条链的结尾都是叶子,我们就按某种顺序把后一条链顶端作为前一条链的结尾的真理捍卫者,最后还剩下内向树的根结点和一个没有真理捍卫者的叶子。于是我们对于环,绕一圈,把后一个内向树根作为前一个内向树剩下的那个叶子的真理捍卫者。

from 官方题解

然后考虑最小值。有个结论,上面的那组解的逆置换就是最小值的解…

为什么呢?感性理解吧… 叶子不能挡路,环上的挡环上的不如挡树里剩下的… 感觉上是符合的…吧?

如何证明它是理论下界啊?

待填坑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
const int maxn=100005;
int n,a[maxn],d[maxn],f[maxn],que[maxn],m;
int lst[maxn],b1[maxn],b2[maxn];
LL ans1,ans2;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]), d[a[i]]++;
for(int i=1;i<=n;i++) if(!d[i]) que[++m]=i;
for(int i=1;i<=m;i++) if(--d[a[que[i]]]==0) que[++m]=a[que[i]];
for(int i=1;i<=n;i++)
if(d[i]&&!f[i]){
int x=i,res=0;
do res++,x=a[x]; while(x!=i);
x=i; while(!f[x]) f[x]=res, x=a[x];
}
for(int i=m;i>=1;i--) f[que[i]]=f[a[que[i]]]+1;
for(int i=1;i<=n;i++) lst[i]=i;
for(int i=1;i<=m;i++){
int x=que[i]; b2[lst[a[x]]]=x; lst[a[x]]=lst[x];
}
for(int i=1;i<=n;i++) if(d[i]) b2[lst[a[i]]]=i;
for(int i=1;i<=n;i++) b1[b2[i]]=i;
for(int i=1;i<=n;i++)
ans2+=f[i], ans1+=lst[i]==i?(d[i]?2:f[i]):1;
printf("%lld\n",ans1);
for(int i=1;i<=n;i++) printf("%d ",b1[i]);
printf("\n%lld\n",ans2);
for(int i=1;i<=n;i++) printf("%d ",b2[i]);
return 0;
}