贪心，递推，线段树，$RMQ$。
假设我们记$ans[i]$是以$i$点为起点对答案的贡献，那么答案就是$sumlimits_{i = 1}^n {ans[i]}$。
$ans[i]$怎么计算呢？
首先，$[i+1,a[i]]$区间上肯定都是$1$（即上图紫线）。
然后在$[i+1,a[i]]$上找到一个$tmp$，使得$tmp$点能够达到的最右端是$[i+1,a[i]]$中最大的，那么$[a[i]+1,a[tmp]]$肯定都是2（即上图绿线）。
然后在$[a[i]+1,a[tmp]]$找一个$tmp2$......依次下去，计算出以$i$为起点对答案的贡献。
但是这样做复杂度太高，需要进行优化。
如果我们知道了$ans[tmp]$，那么就可以$O(1)$知道$ans[i]$，递推一下就可以了。
反过来想，如果我们想知道$ans[i]$，也就是要找到$tmp$，然后从$ans[tmp]$转移过来。
找$tmp$的话可以用线段树，也可以用$RMQ$预处理一下。
$RMQ$：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-6; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-'0'; c=getchar();} } const int maxn=100010; int a[maxn],n,tmp,dp[maxn][30]; LL ans[maxn]; void RMQ_init() { for(int i=0;i<n;i++) dp[i][0]=i; for(int j=1;(1<<j)<=n;j++) for(int i=0;i+(1<<j)-1<n;i++){ if(a[dp[i][j-1]]>a[dp[i+(1<<(j-1))][j-1]]) dp[i][j]=dp[i][j-1]; else dp[i][j]=dp[i+(1<<(j-1))][j-1]; } } int RMQ(int L,int R) { int k=0; while((1<<(k+1))<=R-L+1) k++; if(a[dp[L][k]]>a[dp[R-(1<<k)+1][k]]) return dp[L][k]; return dp[R-(1<<k)+1][k]; } int main() { scanf("%d",&n); for(int i=0;i<n-1;i++) scanf("%d",&a[i]),a[i]--; a[n-1]=n-1; RMQ_init(); ans[n-1]=0; LL d=0; for(int i=n-2;i>=0;i--) { tmp=RMQ(i+1,a[i]); ans[i]=ans[tmp]-(a[i]-tmp)+n-1-a[i]+a[i]-i; d=d+ans[i]; } printf("%lld ",d); return 0; }
线段树：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-6; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-'0'; c=getchar();} } const int maxn=100010; int a[maxn],n,s[4*maxn],M,tmp; LL ans[maxn]; void build(int l,int r,int rt) { if(l==r) { s[rt]=a[l]; return; } int m=(l+r)/2; build(l,m,2*rt); build(m+1,r,2*rt+1); s[rt]=max(s[2*rt],s[2*rt+1]); } void f(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { M=max(M,s[rt]); return; } int m=(l+r)/2; if(L<=m) f(L,R,l,m,2*rt); if(R>m) f(L,R,m+1,r,2*rt+1); } void force(int l,int r,int rt) { if(l==r) {tmp=l; return;} int m=(l+r)/2; if(s[2*rt]==M) force(l,m,2*rt); else force(m+1,r,2*rt+1); } void h(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { if(s[rt]<M) return; force(l,r,rt); return; } int m=(l+r)/2; if(L<=m) h(L,R,l,m,2*rt); if(tmp!=-1) return; if(R>m) h(L,R,m+1,r,2*rt+1); if(tmp!=-1) return; } int main() { scanf("%d",&n); for(int i=1;i<=n-1;i++) scanf("%d",&a[i]); a[n]=n; build(1,n,1); ans[n]=0; LL d=0; for(int i=n-1;i>=1;i--) { M=tmp=-1; f(i+1,a[i],1,n,1); h(i+1,a[i],1,n,1); ans[i]=ans[tmp]-(a[i]-tmp)+n-a[i]+a[i]-i; d=d+ans[i]; } printf("%lld ",d); return 0; }