题目描述

$Yuno$为了方便登山者,在山上造了$N$个营地,编号从$0$开始。

当结界发动时,每当第$i(> 0)$号营地内有人,那么他将被传送到第$A_i(< i)$号营地,如此循环。

所以显然最后只会被传送到第$0$号营地。

但$Kano$并不知晓结界的情况。

他登山的方法是这样的:⾸先分⾝出⼀ 个编号为$D_i$的 Kano,然后将其用投石机抛掷到营地$G_i$。

$Kano$总共做了$M$次这样的登山操作,但每次抛出去的$Kano$都被传送回了营地$0$,所以$Kano$只好放弃了。

但是$Kano$在思考⼀个问题,到底每个营地被多少只编号不同的$Kano$经过过?

输入格式

第⼀⾏两个整数$N,M$,表示山的营地数和登山次数。

接下来$N−1$⾏,每⾏⼀个数,第$i$⾏为$A_i$,表⽰营地$i$将会传向营地$A_i$。

接下来$M$⾏,每⾏两个数$G_i,D_i$。

输出格式

共$N$⾏,每⾏表⽰营地$i$有多少不同编号的$Kano$曾经通过。

数据范围

$N,M\le100000,G_i\le1000000000$。

样例输入

5 4
0
0
1
1
4 1
3 1
2 2
4 2

样例输出

2
2
1
1
2

菜鸡的咆哮

读完题后,我们可以发现:

每个营地经过的$Kano$由两部分组成:发射到该营地上的和从后面营地传送过来的。

显然最后一个营地不会有$Kano$传送进入,当最后一个营地的$Kano$传送走后,倒数第二个营地将不会有$Kano$被传入。

所以我们有了基本思路:

倒序枚举每一个营地,记录当前$Kano$的种数并将其传送到目的地进行更新。

但如果暴力更新的话,我们的时间复杂度是$O(很大)$。

考虑到两个数组相合并,线段树可以满足我们的需求。

于是我们以$Kano$的种类为下表,对每一个营地建立线段树(动态开点)。

每次将起点营地的线段树合并到目的地营地的线段树。

每个营地对应的答案即为其线段树根节点对应的$sum$值。

【注意】

①$Kano$的种类范围很大,所以要先离散化。

②答案要求输出$Kano$的种数而不是$Kano$的总数,所以合并线段树是不能遍往儿子节点跑边更新。

​ 要递归到叶子节点对两个节点进行与运算(保证只有两个状态,有$(1)$与没有$(0)$)。

代码

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
int t[maxn];
struct data{
    int pos;
    int to;
    friend bool operator<(data a,data b){
        return a.pos<b.pos;
    }
}kano[maxn];
//-----------------------------------------
int root[maxn];
int ls[30*maxn];
int rs[30*maxn];
int sum[30*maxn];
void push_up(int k){
    sum[k]=sum[ls[k]]+sum[rs[k]];
}
int tail;
void update(int &k,int l,int r,int x){
    if(!k) k=++tail;
    if(l==r){sum[k]=1;return;}
    int mid=(l+r)>>1;
    if(x<=mid) update(ls[k],l,mid,x);
    else update(rs[k],mid+1,r,x);
    push_up(k);
}
void merge(int &lx,int rx,int l,int r){
    if(!lx||!rx){lx=lx+rx;return;}
    if(l==r){sum[lx]|=sum[rx];return;}
    int mid=(l+r)>>1;
    merge(ls[lx],ls[rx],l,mid);
    merge(rs[lx],rs[rx],mid+1,r);
    push_up(lx);
}
//-----------------------------------------
int main(){
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        scanf("%d",&t[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&kano[i].to,&kano[i].pos);
    }
    sort(kano+1,kano+1+m);
    int pre=kano[1].pos,xx=1;
    kano[1].pos=1;
    for(int i=2;i<=m;i++){
        if(kano[i].pos!=pre) xx++;
        pre=kano[i].pos;
        kano[i].pos=xx;
    }
    for(int i=1;i<=m;i++){
        update(root[kano[i].to],1,xx,kano[i].pos);
    }
    int ans[maxn];
    for(int i=n-1;i>=1;i--){
        ans[i]=sum[root[i]];
        merge(root[t[i]],root[i],1,xx);    
    }
    ans[0]=sum[root[0]];
    for(int i=0;i<n;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}