POI2014 Supercomputer

Supercomputer

POI2014

题意

1.给定一棵N个节点的有根树，根节点为1。

2.有Q次询问，每次给定一个K，用最少的操作次数遍历完整棵树，输出最少操作次数。

3.每次操作可以选择访问不超过K个未访问的点，且这些点的父亲必须在之前被访问过。

4.且第一个次操作必须是根节点

解

1.整个选点的过程大概是这么个样子:
①每次操作，把这一层全部选完
如此一直能够把前i层的点取光

接下来一次不能取完，但是每次都可以找到K个点取
②每次操作，取K个点(可以证明只要选点方式正确肯定可以办到)
如此选点，知道取完

2.如果知道了i
记sum[i]:深度大于等于i的点的总数
那么ans=i+$\lceil\frac{n-sum[i]}{K}\rceil$⌈Kn−sum[i]​⌉

3.怎么找到i
如果现在找到一个i’(i’!=i)
得到ans=i’+$\lceil\frac{sum[i']}{K}\rceil$⌈Ksum[i′]​⌉
如果i’<i
那么本来有些点不能用K取的，被当做用K取而取掉了，导致答案变小
换言之，某些层把父亲和儿子同时取了，导致答案变小

如果i’>i
那么本来有些点应该用K，但是被一次性取关了，导致答案变小了
换言之，某些层一次性取的个数大于K了，导致答案变小

由此观之，则i’或大于i，或小于i，ans皆变小
所以只要找到所有ans中的最大值就行了

4.ans=i+$\lceil\frac{sum[i]}{K}\rceil$⌈Ksum[i]​⌉
当i一定时，K变大，ans必然减小(不变大)
所以对于每个K决策是单调的，
如果当前的i对于上一个K不优，对下一个K也不优

5.保证K一定的情况下，决策单调变优
设x=i,y=sum[i]
ans=x+$\frac{y}{K}$Ky​
K*x-$\frac{K*c}{ans}$ansK∗c​=y
设截距d=-$\frac{K*c}{ans}$ansK∗c​
要让ans最大，就要让d最小
维护一个下凸(使截距单调递增)

具体代码

#include<bits/stdc++.h>
using namespace std;
const int M=1000005;
int n,q,sum[M],K[M],ans[M];
int head[M],asdf,stk[M];
struct edge {
    int to,nxt;
} G[M];
void add_edge(int a,int b) {
    G[++asdf].to=b;
    G[asdf].nxt=head[a];
    head[a]=asdf;
}
int mxdep;
void dfs(int x,int dep) {
    sum[dep]++;
    mxdep=max(mxdep,dep);
    for(int i=head[x]; i; i=G[i].nxt) {
        int y=G[i].to;
        dfs(y,dep+1);
    }
}
bool check(int a,int b,int c) {
    return 1ll*(-sum[a+1]+sum[b+1])*(b-c)>=1ll*(-sum[b+1]+sum[c+1])*(a-b);
}
int main() {
    int a;
    scanf("%d %d",&n,&q);
    for(int i=1; i<=q; i++) {
        scanf("%d",&K[i]);
    }
    for(int i=2; i<=n; i++) {
        scanf("%d",&a);
        add_edge(a,i);
    }
    dfs(1,1);
    for(int i=mxdep; i>=1; i--) {
        sum[i]+=sum[i+1];
    }
    int top=1;
    for(int i=1; i<=mxdep; i++) {
        while(top>1&&check(stk[top-1],stk[top],i))top--;
        stk[++top]=i;
    }
    int pos=1;
    for(int i=1; i<=n; i++) {
        while(pos<top) {
            if(1ll*stk[pos]*i+sum[stk[pos]+1]<=1ll*(stk[pos+1])*i+sum[stk[pos+1]+1])pos++;
            else break;
        }
        ans[i]=stk[pos]+(sum[stk[pos]+1]+i-1)/i;
    }
    for(int i=1; i<=q; i++) {
        if(K[i]>n)printf("%d ",ans[n]);
        else printf("%d ",ans[K[i]]);
    }
    return 0;
}