2020牛客暑期多校训练营（第四场）——ＡAncient Distance

Ancient Distance

题目描述

输入描述

输出描述

For each test case, you should output the sum of all answers instead of each of them.

输入

3
1 2
3
1 1

输出

3
2

说明

The answer for the first test case is {2,1,0}.

The answer for the second test case is {{1,1,0}.

备注
If you have any possible solution, try it bravely!

题目大意

题解

有一个显然的结论，当答案为 x 时，关键点数量≤(𝑛/𝑥+1)+1.因为按照上面的贪心，每次挑选一个关键点时，至少能删除 x+1 个节点。所以对于一个 k，二分上界是 O(n/k)。

我们按顺序枚举 1~k，争取每次验证二分时，把复杂度和 N 剥离开来，搞成和关键点数量有关。

AC代码

#include <bits/stdc++.h>
const int N=2e5+10;
using namespace std;
int n,mxd,f[N],d[N],dp[N],t[N],tot,h[N],v[N],nxt[N],ans[N],id,dfn[N];
void dfs(int x){dfn[++id]=x;for(int i=h[x];~i;i=nxt[i])d[v[i]]=d[x]+1,dfs(v[i]);}
void update(int L,int R,int l,int r)
{if(l>r||L>R) return;if(l==r){for(int i=L;i<=R;i++)ans[i]=l;return;}int mid=L+R>>1;ans[mid]=0;for(int i=0;i<=n;i++)dp[i]=d[i];for(int i=n;i;i--){int x=dfn[i];if(dp[x]==d[x]+mid||i==1)++ans[mid],dp[x]=-1;dp[f[x]]=max(dp[f[x]],dp[x]);}update(L,mid-1,ans[mid],r),update(mid+1,R,l,ans[mid]);
}
int main()
{while(~scanf("%d",&n)){tot=id=mxd=0;memset(h,-1,sizeof(h));for(int i=2;i<=n;i++)scanf("%d",f+i),v[++tot]=i,nxt[tot]=h[f[i]],h[f[i]]=tot;dfs(1);for(int i=1;i<=n;i++) mxd=max(mxd,d[i]);update(0,mxd,1,n);long long cnt=0ll;for(int i=1;i<=mxd;i++) cnt+=1ll*i*(ans[i-1]-ans[i]);printf("%lld\n",cnt);}
}