1 条题解
-
0
考虑设 表示 。
那么考虑与 距离为 的显然是 ，那么长度为 的呢？
发现如果走两步，那么第一步一定走到满足 且 最大的那个 。
这个查询可以直接 st 表。
然后转移方程，就很简单。
因为对于 中所有的点的最短路大小都增加了 ，而中间有一段重复的减掉。
然后就做完了。
代码
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,a[N],st[22][N],cnt[N]; long long ans,f[N]; int ask(int l,int r){ int p=cnt[r-l+1]; int x=st[p][l],y=st[p][r-(1<<p)+1]; return a[x]>a[y]?x:y; } int main(){ scanf("%d",&n); for(int i=1;i<n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)st[0][i]=i; for(int i=1;i<=20;i++)for(int j=1;j+(1<<(i-1))-1<=n;j++){ int x=st[i-1][j],y=st[i-1][j+(1<<(i-1))]; st[i][j]=a[x]>a[y]?x:y; } for(int i=2;i<=n;i++)cnt[i]=cnt[i>>1]+1; for(int i=n-1;i>=1;i--){ int k=ask(i+1,a[i]); f[i]=f[k]+n-i-(a[i]-k); ans+=f[i]; } printf("%lld",ans); }
- 1
