洛谷 5384 「Cnoi 2019」雪松果树

写完才发现这题在我的博客标签分类标准中不能算到任何一个标签内……
于是就塞了一个乱搞的标签。

目前空间最优（逃
其实我这个应该改一改就能改成 O(n) 的了……只是我太懒……

首先有一个简单的思路是按照深度开 vector，每个 vector 内按 DFS 序存，然后每次二分找答案。
但是众所周知 vector 的内存会爆炸。
于是先算出每个深度的点的个数，最后存在一个大数组里就行了。

然后就没了。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6;
const int Q = 1e6;
int n,q;
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct s_query
{
    int k,nxt,ans;
} qry[Q + 5];
int st[N + 5];
inline void push(int u,int k)
{
    static int tot = 0;
    qry[++tot] = (s_query){k,st[u],0},st[u] = tot;
}
int dep[N + 5],cnt[N + 5],a[N + 5],id[N + 5],rk[N + 5],sz[N + 5];
void dfs1(int p)
{
    static int tot = 0;
    rk[id[p] = ++tot] = p,sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        dep[to[i]] = dep[p] + 1,dfs1(to[i]),sz[p] += sz[to[i]];
}
void dfs2(int p)
{
    static int s[N + 5],top = 0;
    s[++top] = p;
    for(register int i = st[p],x;i;i = qry[i].nxt)
        if(qry[i].k >= top)
            qry[i].k = 0;
        else
            x = s[top - qry[i].k],qry[i].k = upper_bound(a + cnt[dep[p] - 1] + 1,a + cnt[dep[p]] + 1,id[x] + sz[x] - 1) - lower_bound(a + cnt[dep[p] - 1] + 1,a + cnt[dep[p]] + 1,id[x]) - 1;
    for(register int i = first[p];i;i = pre[i])
        dfs2(to[i]);
    --top;
}
int main()
{
    scanf("%d%d",&n,&q);
    int u;
    for(register int i = 2;i <= n;++i)
        scanf("%d",&u),add(u,i);
    dfs1(1);
    for(register int i = 1;i <= n;++i)
        ++cnt[dep[i]];
    for(register int i = 1;i <= n;++i)
        cnt[i] += cnt[i - 1];
    for(register int i = 1;i <= n;++i)
        a[++cnt[dep[rk[i]] - 1]] = i;
    for(register int i = 1;i <= n;++i)
        --cnt[dep[i] - 1];
    int k;
    for(register int i = 1;i <= q;++i)
        scanf("%d%d",&u,&k),push(u,k);
    dfs2(1);
    for(register int i = 1;i <= q;++i)
        printf("%d%c",qry[i].k," \n"[i == q]);
}