题意

\(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、关键层的解是最小解。

首先我们按照下面两个规则查询：

1. 如果当前层\(i\)的结点不够\(k\)，则查询完，而且如果之前有\(j < i\)层的点没查询，则查询完。
2. 如果足够了\(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 
    
     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
     
      n?mx:d[a[i]], " \n"[i==Q-1]);    }    return 0;}