题意
\(n(1 \le 1000000)\)个点的有根树，\(1\)号点为根，\(q(1 \le 1000000)\)次询问，每次给一个\(k\)，每一次可以选择\(k\)个未访问的点，且父亲是访问过的，要求最少次数访问完所有的点。
分析
神题不会做。
题解
得到一个式子\(ans=max(i+ \left \lceil \frac{s[i]}{k} \right \rceil), 0 \le i \le maxh\)，其中\(maxh\)是最大深度，\(s[i]\)是深度大于\(i\)的点的数量。证明如下：
定义关键层\(i\)表示拿了\(i\)次后、前\(i\)层已经拿完，以后每一次都可以拿\(k\)个（最后一次除外）。我们需要证明：1、存在关键层。2、关键层的解是最小解。
首先我们按照下面两个规则查询：
- 如果当前层\(i\)的结点不够\(k\)，则查询完，而且如果之前有\(j < i\)层的点没查询，则查询完。
- 如果足够了\(k\)，则在保证最终能在第\(maxh\)次遍历到第\(maxh\)层的情况下，随便选\(k\)个。
那么显然在最后一个执行1操作而且那层\(i\)不存在\(j < i\)层的点没查询的\(i\)就是关键层。由于这样的1操作至少有一个（即第1层肯定是执行的是这样的1操作），所以关键层肯定存在，而且只有一个。
至于关键层的解是否是最小解，感觉很显然，然而不会严格证明。
至于取max，不会严格证明。
最后原题可以转化为\(ans=\left \lceil max(i+\frac{s[i]}{k}) \right \rceil\)，所以按照\(i+\frac{s[i]}{k}\)来斜率优化就行辣。
#include <bits/stdc++.h>
using namespace std;
inline int getint() {
int x=0;
char c=getchar();
for(; c<'0'||c>'9'; c=getchar());
for(; c>='0'&&c<='9'; x=x*10+c-'0', c=getchar());
return x;
}
typedef long long ll;
const int N=1000005;
int a[N], d[N], q[N], c[N], ihead[N], cnt;
struct E {
int next, to;
}e[N];
void add(int x, int y) {
e[++cnt]=(E){ihead[x], y}; ihead[x]=cnt;
}
void dfs(int x) {
for(int i=ihead[x]; i; i=e[i].next) {
d[e[i].to]=d[x]+1;
dfs(e[i].to);
}
}
inline bool ok1(int i, int j, int k) {
return (ll)(c[j]-c[i])*(k-i)>(ll)(c[k]-c[i])*(j-i);
}
inline bool ok2(int b, int j, int k) {
return (ll)b*(j-k)>c[k]-c[j];
}
int main() {
int n=getint(), Q=getint();
for(int i=0; i<Q; ++i) {
a[i]=getint();
}
d[0]=1;
int mx=1;
for(int i=1; i<n; ++i) {
add(getint()-1, i);
}
dfs(0);
for(int i=0; i<n; ++i) {
++c[d[i]-1];
mx=max(mx, d[i]);
}
for(int i=mx; i; --i) {
c[i]+=c[i+1];
}
int *fr=q+1, *ta=q;
for(int i=1; i<=mx; ++i) {
for(; fr<ta && ok1(*(ta-1), i, *ta); --ta);
*++ta=i;
}
for(int i=1; i<=n; ++i) {
for(; fr<ta && ok2(i, *(fr+1), *fr); ++fr);
d[i]=*fr+(c[*fr]+i-1)/i;
}
for(int i=0; i<Q; ++i) {
printf("%d%c", a[i]>n?mx:d[a[i]], " \n"[i==Q-1]);
}
return 0;
}