【dfs序+树上差分】ABC309 E

╰半橙微兮° 2024-03-17 17:44 112阅读 0赞

[E - Family and Insurance (atcoder.jp)][E - Family and Insurance _atcoder.jp]

题意：

![b5454fe77bed4f26af4f8ce1f8e58714.png][]

思路：

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

不同的是是对一部分子树操作，因此对于离子树根结点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;
    }

[E - Family and Insurance _atcoder.jp]: https://atcoder.jp/contests/abc309/tasks/abc309_e
[b5454fe77bed4f26af4f8ce1f8e58714.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1bbacc76fec44efbaf079e1f4cfcefee.png