牛客多校4 A Ancient Distance線分樹+dfs序
2312 ワード
構想はある巨男に由来する:巨男ブログ
1<=k<=nの答えが最大でn-1が最小で0なので、大きな値から小さな値を列挙し(これで小さい値は大きな値を上書きします)、この答えに対応する最小kがどれだけ最後に接頭辞の最小値をすればいいかを見てみましょう.
最小kに対応するansを探す過程は欲張りに違いない深さ最大の点を見つけてansステップ(ans級の祖先を探す)を上り、サブツリーをマークすればいい.
最大深さ<=nowansでループを終了
ansが決定したときに最大n/(ans+1)回の操作を行う各操作の複雑さはlognレベルである
従って総複雑度はnlogn^2(調和級数の和はlognレベル)である.
1<=k<=nの答えが最大でn-1が最小で0なので、大きな値から小さな値を列挙し(これで小さい値は大きな値を上書きします)、この答えに対応する最小kがどれだけ最後に接頭辞の最小値をすればいいかを見てみましょう.
最小kに対応するansを探す過程は欲張りに違いない深さ最大の点を見つけてansステップ(ans級の祖先を探す)を上り、サブツリーをマークすればいい.
最大深さ<=nowansでループを終了
ansが決定したときに最大n/(ans+1)回の操作を行う各操作の複雑さはlognレベルである
従って総複雑度はnlogn^2(調和級数の和はlognレベル)である.
#include
using namespace std;
const int N = 2e5+100;
vectorg[N],st;
int tot,in[N],out[N],n,ans[N],rnk[N];
int fa[N][22],dep[N];
typedef long long ll;
void init(){
tot=0;
for(int i = 1; i <= n; i++) g[i].clear(),ans[i]=n-1;
}
void dfs(int u,int f){
rnk[in[u]=++tot]=u;
dep[u]=dep[f]+1;
fa[u][0]=f;
for(int i = 1; i <= 19; i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto v:g[u]){
if(v==f) continue;
dfs(v,u);
}
out[u]=tot;
}
int kth(int u,int k){
int bit=0;
while(k){
if(k&1) u=fa[u][bit];
k>>=1;
bit++;
}
return u;
}
struct segTree{
int nd,mx;
bool cov;
}T[N<<2];
#define ls id<<1
#define rs ls|1
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
void pushup(int id){
T[id].mx=0;
if(!T[ls].cov&&T[ls].mx>T[id].mx) T[id]=T[ls];
if(!T[rs].cov&&T[rs].mx>T[id].mx) T[id]=T[rs];
}
void update(int id,int l,int r,int L,int R,int v){
if(L<=l&&R>=r){
T[id].cov=v;
return;
}
if(L<=mid) update(lson,L,R,v);
if(R>mid) update(rson,L,R,v);
pushup(id);
}
void build(int id,int l,int r){
T[id].cov=false;
if(l==r){
T[id].mx=dep[T[id].nd=rnk[l]];
return;
}
build(lson);build(rson);
pushup(id);
}
int main(){
while(~scanf("%d",&n)){
init();
for(int i = 2; i <= n; i++){
int x;
scanf("%d",&x);
g[i].push_back(x);
g[x].push_back(i);
}
dep[0]=-1;dfs(1,0);
build(1,1,n);
for(int nowans=n-1; nowans >= 0; nowans--){
int ndcos=0;
st.clear();
while(1){
ndcos++;
if(T[1].mx<=nowans) break;
int u = T[1].nd;
u = kth(u,nowans);
update(1,1,n,in[u],out[u],1);
st.push_back(u);
}
ans[ndcos]=nowans;
for(auto v:st) update(1,1,n,in[v],out[v],0);
}
for(int i = 2; i <= n; i++) ans[i]=min(ans[i],ans[i-1]);
ll sum=0;
for(int i = 1; i <= n; i++) sum+=ans[i];
printf("%lld
",sum);
}
return 0;
}