求捉虫

TLEWA @ 2023-03-21 22:03:40

by TLEWA @ 2023-03-21 22:03:55

#include<bits/stdc++.h>
#define mod M
using namespace std;

int N,M,R,P;

int read(){int x;cin >> x;return x;}

const int maxn=100005;
vector<int> tre1[maxn]; //存图数组 

int arr[maxn]; //初始数据数组 
int fa[maxn],size[maxn],dep[maxn],son[maxn],dfn[maxn],top[maxn]; //树的变量 

//线段树 
struct Tree {
    int l,r;
    long long add=0,sum=0;
}tre[maxn*4];

inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}

void pushup(int x) {tre[x].sum=(tre[ls(x)].sum+tre[rs(x)].sum)%mod;}
void pushdown(int x) {
    auto &root=tre[x],&lson=tre[ls(x)],rson=tre[rs(x)];
    if(root.add) {
        lson.add=root.add,lson.sum+=root.add*(lson.r-lson.l+1);
        lson.add%=mod;
        rson.add=root.add,rson.sum+=root.add*(rson.r-rson.l+1);
        rson.add%=mod;
        root.add=0;
    }
}

//建树操作 
void build(int x,int l,int r) {
    tre[x].l=l,tre[x].r=r,tre[x].add=0,tre[x].sum=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
}

//线段树常规操作
void plu(int u,int l,int r,int k) { //区间加 
    if(l<=tre[u].l&&r>=tre[u].r) tre[u].add+=k,tre[u].sum+=k*(tre[u].r-tre[u].l+1);
    else {
        pushdown(u);
        int mid=(tre[u].l+tre[u].r)/2;
        if(l<=mid) plu(ls(u),l,r,k);
        if(r>mid) plu(rs(u),l,r,k);
        pushup(u);
    }
}

long long query(int u,int l,int r) { //区间加 
    if(l<=tre[u].l&&r>=tre[u].r) return tre[u].sum%mod;
    pushdown(u);
    int mid=(tre[u].l+tre[u].r)/2;
    long long summ=0;
    if(l<=mid) summ+=query(ls(u),l,r);
    if(mid<r) summ+=query(rs(u),l,r);
    cout << summ << endl;
    summ%=mod;
    return summ;
}

//树链刨分操作
void plus_path(int u,int v,int k) {
    k%=mod;
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        plu(1,dfn[top[u]],dfn[u],k);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    plu(1,dfn[u],dfn[v],k);
}

long long query_path(int u,int v) {
    long long summ=0;
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        summ+=query(1,dfn[top[u]],dfn[u]);
        summ%=mod;
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    summ+=query(1,dfn[u],dfn[u]);
    summ%=mod;
    return summ;
}

void plus_tree(int u,int k) {
    plu(1,dfn[u],dfn[u]+size[u]-1,k);
}

long long query_tree(int u) {
    return query(1,dfn[u],dfn[u]+size[u]-1);
}

//dfs
void dfs1(int now,int father) {
    fa[now]=father;
    size[now]=1;
    dep[now]=dep[father]+1;

    int mson=0;
    for(auto i:tre1[now]) {
        if(i==father) continue;
        dfs1(i,now);
        size[now]+=size[i];
        if((son[now]==0||size[son[now]]<size[i]) || (size[son[now]]==size[i]&&son[now]>i)) son[now]=i;
    }
}

int cnt;
void dfs2(int now,int t_fa) {
    dfn[now]=++cnt;
    top[now]=t_fa;
    plu(1,dfn[now],dfn[now],arr[now]);
    if(son[now]) {
        dfs2(son[now],t_fa);
        for(auto i:tre1[now]) {
            if(son[now]==i||i==fa[now]) continue;
            dfs2(i,i);
        }
    }
}

int main() {
    cin >> N >> M >> R >> P;
    for(int i=1;i<=N;++i) cin >> arr[i];
    int x,y;
    for(int i=1;i!=N;++i) {
        cin >> x >> y;
        tre1[x].push_back(y);
        tre1[y].push_back(x);
    }
    build(1,1,N);
    dfs1(R,0);
    dfs2(R,R);
//  cout << 111;

    int op,u,v,k;
    while(M--) {
        cin >> op;
        if(op==1) {
            cin >> u >> v >> k;
            plus_path(u,v,k);
        }else if(op==2) {
            cin >> u >> v;
            cout << query_path(u,v) << endl;
        }else if(op==3) {
            cin >> u >> k;
            plus_tree(u,k);
        }else {
            cin >> u;
            cout << query_tree(u) << endl;
        }
    }

    return 0;
}

by TLEWA @ 2023-03-21 22:07:09

悬赏一关注

by hgzxwzf @ 2023-03-21 22:11:23

push_down写错了吧，左右儿子的标记是加上自己的标记，不是等于。

by TLEWA @ 2023-03-21 22:24:09

@hgzxwzf 谢谢！已关注

by TLEWA @ 2023-03-21 22:25:17

但是问题还是没有解决...

by hgzxwzf @ 2023-03-21 22:56:07

你的rson咋没加引用