nove.13 月下毛景树 [树剖]

月下毛景树 复健记录

树剖，权值下放
树剖的准备：
第一次DFS，可以记录深度、子树大小、父亲、重儿子；
第二次可以记录重链顶、DFS序

本题需要维护的数组：
区间最大值
lazy_tag，有覆盖、加

*重点：覆盖优先级高于区间加
如果先区间加再覆盖，区间加的效果就被覆盖掉了

需要支持单点修改、区间覆盖、区间加、区间查询

打代码的时候的一些细节：
根是谁不重要，让他是1就好了
dfn的反函数是idx
u,v在同一条链上时，（假设dfn[u]<dfn[v]）操作区间不能把u算进去：考虑下放权值操作，节点u上的数据不属于u,v之间的链
第二次DFS，遍历非重儿子的时候，记得排除重儿子

#include<bits/stdc++.h>
using namespace std;
#define in Read()

int in{
    int i=0,f=1; char ch=0;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=1e6+5;
const int INF=2147483647;
int n;
int to1[N],to2[N],e_wei[N];
int faz[N],son[N],siz[N],dep[N];
int dfn[N],top[N],cnt,idx[N];
int wei[N],dwn[N];
vector<int>G[N];

struct node{
    int max,cov,add;
}tre[N<<2];

void DFS1(int u,int fa){
    faz[u]=fa;
    siz[u]=1;
    dep[u]=dep[fa]+1;
    for(auto v:G[u]){
        if(v==fa) continue;
        DFS1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
    return;
}

void DFS2(int u,int tp){
    top[u]=tp;
    dfn[u]=++cnt;
    idx[cnt]=u;
    if(!son[u]) return;
    DFS2(son[u],tp);
    for(auto v:G[u]){
        if(v==faz[u]||v==son[u]) continue;
        DFS2(v,v);
    }
    return;
}

void put_down(){
    for(int i=1;i<n;++i){
        dwn[i]=dep[to1[i]]<dep[to2[i]]?to2[i]:to1[i];
        wei[dwn[i]]=e_wei[i];
    }
}

#define lch p<<1
#define rch p<<1|1

void push_up(int p){
    tre[p].max=max(tre[lch].max,tre[rch].max);
}

void push_down(int p){
    if(tre[p].cov!=-1){
        tre[lch].max=tre[p].cov;
        tre[rch].max=tre[p].cov;
        tre[lch].cov=tre[p].cov;
        tre[rch].cov=tre[p].cov;
        tre[lch].add=0;
        tre[rch].add=0;
        tre[p].cov=-1;
    }
    if(tre[p].add){
        tre[lch].add+=tre[p].add;
        tre[rch].add+=tre[p].add;
        tre[lch].max+=tre[p].add;
        tre[rch].max+=tre[p].add;
        tre[p].add=0;
    }
}

void build(int p,int l,int r){
    tre[p].cov=-1;
    tre[p].add=0;
    tre[p].max=-INF;
    if(l==r){
        tre[p].max=wei[idx[l]];
        return;
    }
    int mid=l+r>>1;
    build(lch,l,mid);
    build(rch,mid+1,r);
    push_up(p);
}

int query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R) return tre[p].max;
    push_down(p);
    int res=-INF;
    int mid=l+r>>1;
    if(L<=mid) res=max(res,query(lch,l,mid,L,R));
    if(R>mid) res=max(res,query(rch,mid+1,r,L,R));
    return res;
}

void cover(int p,int l,int r,int L,int R,int w){
    if(L<=l&&r<=R){ tre[p].max=w, tre[p].cov=w, tre[p].add=0; return;}
    push_down(p);
    int mid=l+r>>1;
    if(L<=mid) cover(lch,l,mid,L,R,w);
    if(R>mid) cover(rch,mid+1,r,L,R,w);
    push_up(p);
}

void add(int p,int l,int r,int L,int R,int w){
    if(L<=l&&r<=R){ tre[p].max+=w, tre[p].add+=w; return;}
    push_down(p);
    int mid=l+r>>1;
    if(L<=mid) add(lch,l,mid,L,R,w);
    if(R>mid) add(rch,mid+1,r,L,R,w);
    push_up(p);
}

#undef lch
#undef rch

int Query(int u,int v){
    int ans=-INF;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ans=max(ans,query(1,1,cnt,dfn[top[u]],dfn[u]));
        u=faz[top[u]];
    }
    if(u==v) return ans;
    if(dep[u]<dep[v]) swap(u,v);
    ans=max(ans,query(1,1,cnt,dfn[v]+1,dfn[u]));
    return ans;
}

void Cover(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        cover(1,1,cnt,dfn[top[u]],dfn[u],w);
        u=faz[top[u]];
    }
    if(u==v) return;
    if(dep[u]<dep[v]) swap(u,v);
    cover(1,1,cnt,dfn[v]+1,dfn[u],w);
}

void Add(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        add(1,1,cnt,dfn[top[u]],dfn[u],w);
        u=faz[top[u]];
    }
    if(u==v) return;
    if(dep[u]<dep[v]) swap(u,v);
    add(1,1,cnt,dfn[v]+1,dfn[u],w);
}

int main(){

    // freopen("1.in","r",stdin);

    n=in;
    for(int i=1;i<n;++i){
        int u=in,v=in,w=in;
        to1[i]=u, to2[i]=v;
        e_wei[i]=w;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    DFS1(1,0);
    DFS2(1,1);
    put_down();
    build(1,1,cnt);

    string opt;
    cin>>opt;
    while(opt!="Stop"){
        if(opt=="Max"){ 
            int u=in,v=in;
            printf("%d\n",Query(u,v));
        }
        if(opt=="Cover"){
            int u=in,v=in,w=in;
            Cover(u,v,w);
        }
        if(opt=="Change"){
            int x=in,w=in;
            cover(1,1,cnt,dfn[dwn[x]],dfn[dwn[x]],w);
        }
        if(opt=="Add"){
            int u=in,v=in,w=in;
            Add(u,v,w);
        }
        cin>>opt;
    }
    
}

比较满意，两个小时调出来，轻度看题解
有进步，加油頑張る！