(POI) XXI OI Round II - day 1 Task Supercomputer

https://szkopul.edu.pl/problemset/problem/e9ycK_efBDBt4aPs-QeqYpwR/site/?key=statement

看了中國大神們的解釋之後，終於寫出來了

附個網址：http://victorwonder.is-programmer.com/posts/80059.html

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N = 1000006;

int depth[N];
int s[N];
int par[N];

int q[N];
long long ans[N];

typedef long long LL;

struct L
{
    LL m;
    LL b;
    L(LL _m,LL _b):m(_m),b(_b){}
    LL val(LL x)
    {
        return m*x+b;
    }
};

bool check(L a,L b,L c)
{
    return (a.m - b.m) * (a.b - c.b) > (a.b - b.b) * (a.m - c.m);
}

int main ()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;m>=i;i++)
    {
        scanf("%d",&q[i]);
    }
    depth[1] = 1;
    s[0]++;
    int mx_depth = 0;
    for (int i=2;n>=i;i++)
    {
        scanf("%d",&par[i]);
        depth[i] = depth[par[i]] + 1;
        s[depth[i]-1]++;
        mx_depth = max(mx_depth,depth[i]);
    }
    for (int i=mx_depth;i>=1;i--)
    {
        s[i] += s[i+1];
    }
    //version O(n*k)
    //ans = max(i + ceil((s[i])/k))
    //ans = max(ceil((k*i + s[i])/k))
    /*
    70pts www
    for (int i=1;m>=i;i++)
    {
        int ans = 0;
        for (int j=1;mx_depth>=j;j++)
        {
            ans = max(ans,(j) + (s[j]+q[i]-1)/q[i]);
        }
        printf("%d",ans);
        if (i==m) puts("");
        else putchar(' ');
    }
    */
    deque<L> dq;
    #define SZ(x) ((int)(x).size())
    for (int i=1;mx_depth >= i;i++)
    {
        L line = L(i,s[i]);
        line.m = i;
        line.b = s[i];
        while (SZ(dq) >= 2 && check(dq[SZ(dq)-2],dq[SZ(dq)-1],line))
        {
            dq.pop_back();
        }
        dq.push_back(line);
    }
    for (int i=1;n>=i;i++)
    {
        while (SZ(dq) >= 2 && dq[0].val(i) < dq[1].val(i))
        {
            dq.pop_front();
        }
        ans[i] = dq[0].val(i);
        ans[i] = (ans[i] + i-1)/i;
    }
    for (int i=n + 1;1000000>=i;i++)
    {
        ans[i] = ans[i-1];
    }
    for (int i=1;m>=i;i++)
    {
        printf("%lld",ans[q[i]]);
        if (i==m) puts("");
        else putchar(' ');
    }
}