2020牛客多校第四场 A-Ancient Distance（二分答案+骚操作

题意：https://ac.nowcoder.com/acm/contest/5669/A

给你一个k，表示你能选的关键点数，树上每个节点的值为最近关键祖先的距离，问k分别为（1~n）时，所有节点值最大值最小化后的和

思路：

首先考虑一个K，肯定是二分答案-最值，check时每次从叶子选一个距离最大的能向上跳dis步就跳，跳到的那个点线段树里直接删掉（线段树恢复的话，vector计个你动过哪些点，还原回去就行了）这样的话应该是，nloglogloglog的（大概吧，二分dis+倍增求k祖先+线段树查询+更新+k的调和级数次查找，不过求k级祖先和线段树更新是一个log，不懂不懂）

但是有骚操作

我们反过来枚举dis，就是保存 k 个点极限情况下能让max降到最少多少，然后显然跑一遍前缀min，可以少一个log（关键在100~102行）

  1 #include <bits/stdc++.h>
  2 #define rep(i,x,n) for(int i=x;i<=n;i++)
  3 #define rson mid+1,r,p<<1|1
  4 #define lson l,mid,p<<1
  5 #define ll long long
  6 #define pb push_back
  7 using namespace std;
  8 const int N=(int)2e5+10;
  9 int n;
 10 vector<int>g[N];
 11 int d[N],f[N][20],L[N],R[N],pos[N],tot;
 12 int A[N<<2],B[N<<2],tag[N<<2];
 13 int ans[N],lg[N];
 14 vector<int>v;
 15 int mx(int x,int y){
 16     if(d[x]>d[y]) return x;
 17     else return y;
 18 }
 19 void bd(int l,int r,int p){
 20     tag[p]=0;
 21     if(l==r) return A[p]=B[p]=pos[l],void();
 22     int mid=l+r>>1;
 23     bd(lson);bd(rson);
 24     A[p]=B[p]=mx(A[p<<1],A[p<<1|1]);
 25 }
 26 void pd(int p){
 27     v.pb(p<<1);v.pb(p<<1|1);
 28     A[p<<1]=A[p<<1|1]=0;
 29     tag[p<<1]=tag[p<<1|1]=1;
 30     tag[p]=0;
 31 }
 32 void up(int dl,int dr,int l,int r,int p){
 33     v.pb(p);
 34     if(l==dl&&r==dr){
 35         tag[p]=1;
 36         A[p]=0;
 37         return;
 38     }
 39     int mid=l+r>>1;
 40     if(tag[p]) pd(p);
 41     if(dr<=mid) up(dl,dr,lson);
 42     else if(dl>mid) up(dl,dr,rson);
 43     else up(dl,mid,lson),up(mid+1,dr,rson);
 44     A[p]=mx(A[p<<1],A[p<<1|1]);
 45 }
 46 void dfs(int u,int fa){
 47     d[u]=d[fa]+1;
 48     f[u][0]=fa;
 49     for(int i=1;(1<<i)<=n;i++){
 50         f[u][i]=f[f[u][i-1]][i-1];
 51     }
 52     L[u]=++tot;pos[tot]=u;
 53     for(int x:g[u]){
 54         if(x==fa) continue;
 55         dfs(x,u);
 56     }
 57     R[u]=tot;
 58 }
 59 int find(int x,int k){
 60     for(int i=lg[k];i>=0;i--){
 61         if(k>=(1<<i)){
 62             k-=(1<<i);
 63             x=f[x][i];
 64         }
 65     }
 66     if(!x) x=1;
 67     return x;
 68 }
 69 int ck(int mid){
 70     v.clear();
 71     int cnt=0;
 72     while(1){
 73         int x=A[1];
 74         if(x==0) break;
 75         int y=find(x,mid);
 76         ++cnt;
 77         up(L[y],R[y],1,n,1);
 78     }
 79     for(int p:v){
 80         A[p]=B[p];
 81         tag[p]=0;
 82     }
 83     return cnt;
 84 }
 85 int main(){
 86     for(int i=2;i<N;i++) lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
 87     while(~scanf("%d",&n))
 88     {
 89         tot=0;
 90         rep(i,2,n)
 91         {
 92             int x;
 93             scanf("%d",&x);
 94             g[x].pb(i);
 95         }
 96         dfs(1,0);
 97         bd(1,n,1);
 98         rep(i,1,n) ans[i]=n+1;
 99         ll Ans=0;
100         for(int i=n-1;i>=0;i--) ans[ck(i)]=i;
101         for(int i=2;i<=n;i++) ans[i]=min(ans[i-1],ans[i]);
102         for(int i=1;i<n;i++) Ans+=ans[i];
103         printf("%lld
",Ans);
104         rep(i,1,n) g[i].clear();
105     }
106     return 0;
107 }