树剖学习 （2） & 做题记录 P3950 部落冲突

· · 算法·理论

博客跳转。

不要问我 （1） 去哪里了，在咕咕咕。

看完后可以看着下面的图再自己独立推一次。

看完后完成 P3950。

:::success[P3950 代码]

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
const int MN=3*1e5+10;
LL tree[MN*8],tag[MN*8];
int n,m,p,q,x;
char op;
vector<int>tu[MN];
int fa[MN],top[MN],dep[MN],son[MN],siz[MN],id[MN],idx;
int root=1,k=0;
vector<pair<int,int>>E/*vent*/;
void dfs(int &now,int &fat){
    fa[now]=fat;dep[now]=dep[fat]+1;siz[now]=1;
    for(auto &x:tu[now]){
        if(x!=fat){
            dfs(x,now);
            siz[now]+=siz[x];
            if(siz[x]>siz[son[now]]){
                son[now]=x;
            }
        }
    }
    return;
}
void dfs2(int &now,int &fr){
    id[now]=++idx;top[now]=fr;
    if(son[now])dfs2(son[now],fr);
    for(auto &x:tu[now]){
        if(x!=son[now]&&x!=fa[now]){
            dfs2(x,x);
        }
    }
    return;
}
void push_up(int &now){
    tree[now]=tree[now*2]+tree[now*2+1];
    return;
}
void push_down(int &now,int &ll,int &lr,int rl,int &rr){
    if(!tag[now])return;
    tag[now*2]+=tag[now];
    tag[now*2+1]+=tag[now];
    tree[now*2]+=(lr-ll+1)*tag[now];
    tree[now*2+1]+=(rr-rl+1)*tag[now];
    tag[now]=0;
    return;
}
bool inli(int &l,int &r,int &xl,int &xr){
    return l>=xl&&xr>=r;
}
void change(int now,int l,int &r,int &xl,int &xr,int &add){
    if(inli(l,r,xl,xr)){
        tree[now]+=(r-l+1)*add;
        tag[now]+=add;
        return;
    }
    int mid=l+(r-l)/2;
    push_down(now,l,mid,mid+1,r);
    if(mid>=xl)change(now*2,l,mid,xl,xr,add);
    if(mid<xr)change(now*2+1,mid+1,r,xl,xr,add);
    push_up(now);
    return;
}
LL query(int now,int l,int &r,int &xl,int &xr){
    if(inli(l,r,xl,xr)){
        return tree[now];
    }
    LL sum=0;
    int mid=l+(r-l)/2;
    push_down(now,l,mid,mid+1,r);
    if(mid>=xl)sum+=query(now*2,l,mid,xl,xr);
    if(mid<xr)sum+=query(now*2+1,mid+1,r,xl,xr);
    push_up(now);
    return sum;
}
LL get_query(int &x,int &y){
    LL sum=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        sum+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
        if(sum>0)return 1;
        //cout<<x<<" "<<y<<"\n";
    }
    if(id[x]<id[y])swap(x,y);
    int l=id[y]+1;
    if(id[y]+1<=id[x])sum+=query(1,1,n,l,id[x]);
    return sum;
}
void get_change(int &x,int &y,int add){
    // while(top[x]!=top[y]){
    //     if(dep[top[x]]<dep[top[y]])swap(x,y);
    //     change(1,1,n,top[x],id[x],add);
    //     x=fa[top[x]];
    //     cout<<x<<" "<<y<<"\n";
    // }
    if(id[x]<id[y])swap(x,y);
    change(1,1,n,id[x],id[x],add);
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        cin>>p>>q;
        tu[p].emplace_back(q);
        tu[q].emplace_back(p);
    }
    dfs(root,k);
    dfs2(root,root);
    while(m--){
        cin>>op;
        if(op=='Q'){
            cin>>p>>q;
            cout<<(get_query(p,q)==0?"Yes\n":"No\n");
        }
        else if(op=='C'){
            cin>>p>>q;
            get_change(p,q,1);
            E.push_back({p,q});
        }
        else{
            cin>>x;
            get_change(E[x-1].first,E[x-1].second,-1);
        }
    }
    return 0;
}

/*
｀　　　　　　　　　　　　　　　　　　　　　　　４　　　　０００　　　　　　４
　　　　　　　　　　　　　　　　　　　　　　　４４　　　０　　　０　　　　４４
ｘ　　　ｘ　　ｙ　　　ｙ　　ｘ　　　ｘ　　　　４４　　　０　　　０　　　　４４
ｘ　　　ｘ　　ｙ　　　ｙ　　ｘ　　　ｘ　　　４　４　　　０　　　０　　　４　４
　ｘ　ｘ　　　ｙ　　　ｙ　　　ｘ　ｘ　　　　４　４　　　０　　　０　　　４　４
　　ｘ　　　　　ｙ　ｙ　　　　　ｘ　　　　４　　４　　　０　　　０　　４　　４
　ｘ　ｘ　　　　ｙ　ｙ　　　　ｘ　ｘ　　　４４４４４　　０　　　０　　４４４４４
ｘ　　　ｘ　　　　ｙ　　　　ｘ　　　ｘ　　　　　４　　　０　　　０　　　　　４
ｘ　　　ｘ　　　　ｙ　　　　ｘ　　　ｘ　　　　　４　　　　０００　　　　　　４
　　　　　　　ｙｙ
*/

:::

再写完后可以写 P3038，这题是保证查询的两个节点直接相连，但是不保证修改的直接相连，可以尝试写。