【dfs序+树上差分】ABC309 E-蒲公英云

【dfs序+树上差分】ABC309 E

E - Family and Insurance (atcoder.jp)

题意：

思路：

对子树进行操作，就可以树上差分

不同的是是对一部分子树操作，因此对于离子树根结点d+1距离的在子树内的结点进行减操作

然后做一次前缀和就行

至于如何判断一个点是否在子树内，只需求出dfs序即可

这里lca判断会多个log，会超时

Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mxn=1e6+10;
const int mxe=1e6+10;
const int mod=1e9+7;
const int Inf=1e18;
struct ty{
    int to,next;
}edge[mxe<<2];
vector<int> V[mxn];
int N,M,tot=0,idx=0;
int x,y;
int Fa[mxn],b[mxn];
int head[mxn],dep[mxn],ans[mxn],F[mxn][33];
int In[mxn],sz[mxn];
void add(int u,int v){
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void G_init(){
    tot=0;
    for(int i=0;i<=N;i++){
        head[i]=-1;
    }
}
void dfs(int u,int fa){
    In[u]=++idx;
    sz[u]=1;
    dep[u]=dep[fa]+1;
    for(int i=head[u];~i;i=edge[i].next){
        if(edge[i].to==fa) continue;
        dfs(edge[i].to,u);
        sz[u]+=sz[edge[i].to];
    }
}
void dfs2(int u,int fa){
    ans[u]=ans[fa]+b[u];
    for(int i=head[u];~i;i=edge[i].next){
        if(edge[i].to==fa) continue;
        dfs2(edge[i].to,u);
    }
}
bool check(int u,int v){
    return In[v]>=In[u]&&In[v]<=In[u]+sz[u]-1;
}
void solve(){
    cin>>N>>M;
    G_init();
    for(int i=2;i<=N;i++){
        cin>>Fa[i];
        add(i,Fa[i]);
        add(Fa[i],i);
    }
    dfs(1,0);
    int mx=-1;
    for(int i=1;i<=N;i++) mx=max(mx,dep[i]);
    for(int i=1;i<=N;i++) V[dep[i]].push_back(i);
    for(int i=1;i<=M;i++){
        cin>>x>>y;
        b[x]++;
        if(dep[x]+y+1<=mx){
            for(auto it:V[dep[x]+y+1]){
                if(check(x,it)) b[it]--;
            }
        }
    }
    ans[1]=b[1];
    dfs2(1,0);
    int cnt=0;
    for(int i=1;i<=N;i++){
        if(ans[i]!=0) cnt++;
    }
    cout<<cnt<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}