社区讨论

萌新刚学oi,这道题全wa,求dalao帮助

P4315月下“毛景树”参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lobmruur
此快照首次捕获于
2023/10/29 23:33
2 年前
此快照最后确认于
2023/11/04 04:22
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int first[N],nxt[N<<1],to[N<<1],wei[N<<1],cnt;
inline void addedge(int u,int v,int w){
    nxt[++cnt]=first[u];first[u]=cnt;
    to[cnt]=v;wei[cnt]=w;
}
struct edge{
    int u,v,w;
}e[N];
int n,m;
int hson[N],siz[N],dep[N],fa[N],val[N];
void dfs1(int u,int f){
    fa[u]=f;siz[u]=1;
    for(int i=first[u];i;i=nxt[i]){
        int v=to[i],w=wei[i];
        if(v==f) continue;
        dep[v]=dep[u]+1;
        val[v]=w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[hson[u]]) hson[u]=v;
    }
}
int top[N],st[N],pre[N],tot;
void dfs2(int u,int tp){
    // cout<<u<<' '<<tp<<endl;
    top[u]=tp;st[u]=++tot;pre[tot]=u;
    if(hson[u]) dfs2(hson[u],tp);
    for(int i=first[u];i;i=nxt[i])
        if(to[i]!=fa[u]&&to[i]!=hson[u])
            dfs2(to[i],to[i]);
}

#define lc p<<1
#define rc p<<1|1
struct node{
    int maxn,lazy1,lazy2;
}t[N<<2];
inline void pushup(int p){
    return void(t[p].maxn=max(t[lc].maxn,t[rc].maxn));
}
inline void pushnow1(int p,int v){
    t[p].lazy1=v;t[p].lazy2=0;
    t[p].maxn=v;
}
inline void pushnow2(int p,int v){
    if(t[p].lazy1){
        t[p].lazy1+=v;t[p].maxn+=v;
    }
    else t[p].maxn+=v,t[p].lazy2+=v;
}
inline void pushdown(int p){
    if(t[p].lazy1){
        pushnow1(lc,t[p].lazy1);
        pushnow1(rc,t[p].lazy1);
        t[p].lazy1=0;
    }
    if(t[p].lazy2){
        pushnow2(lc,t[p].lazy2);
        pushnow2(rc,t[p].lazy2);
        t[p].lazy2=0;
    }
}
inline void build(int p,int l,int r){
    if(l==r) return void(t[p].maxn=val[pre[l]]);
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    return pushup(p);
}
inline void change(int p,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr) return pushnow1(p,v);
    pushdown(p);
    int mid=l+r>>1;
    if(ql<=mid) change(lc,l,mid,ql,qr,v);
    if(qr>mid) change(rc,mid+1,r,ql,qr,v);
    return pushup(p);
}
inline void add(int p,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr) return pushnow2(p,v);
    pushdown(p);
    int mid=l+r>>1;
    if(ql<=mid) add(lc,l,mid,ql,qr,v);
    if(qr>mid) add(rc,mid+1,r,ql,qr,v);
    return pushup(p);
}
inline int query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return t[p].maxn;
    // cout<<"@#$$"<<t[p].maxn<<endl;
    pushdown(p);
    int mid=l+r>>1,ans=0;
    if(ql<=mid) ans=max(ans,query(lc,l,mid,ql,qr));
    if(qr>mid) ans=max(ans,query(rc,mid+1,r,ql,qr));
    return ans;
}
inline void change(int x,int y,int v){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(1,1,n,st[top[x]],st[x],v);
        x=fa[top[x]];
    }
    if(x==y) return;
    if(dep[x]>dep[y]) swap(x,y);
    return change(1,1,n,st[x]+1,st[y],v);
}
inline void add(int x,int y,int v){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        add(1,1,n,st[top[x]],st[x],v);
        x=fa[top[x]];
    }
    if(x==y) return;
    if(dep[x]>dep[y]) swap(x,y);
    return add(1,1,n,st[x]+1,st[y],v);
}
inline int query(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=max(ans,query(1,1,n,st[top[x]],st[x]));
        x=fa[top[x]];
    }
    // cout<<"$%^&%^&";
    // cout<<x<<' '<<y<<endl;
    if(x==y) return ans;
    if(dep[x]>dep[y]) swap(x,y);
    ans=max(ans,query(1,1,n,st[x]+1,st[y]));
    return ans;
}
inline int rd(){
    char c=getchar();
    int v=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') v=(v<<3)+(v<<1)+(c^48),c=getchar();
    return v;
}
int main(){
    n=rd();
    for(int i=1;i<n;++i){
        int u=rd(),v=rd(),w=rd();
        e[i]=(edge){u,v,w};
        addedge(u,v,w);addedge(v,u,w);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(1){
        char c=getchar();
        while(c<'A'||c>'Z') c=getchar();
        if(c=='S') break;
        if(c=='C'){
            c=getchar();
            if(c=='h') {int x=rd(),v=rd();change(1,1,n,dep[e[x].u]>dep[e[x].v]?st[e[x].u]:st[e[x].v],dep[e[x].u]>dep[e[x].v]?st[e[x].u]:st[e[x].v],v);}
            else{int x=rd(),y=rd(),v=rd();change(x,y,v);}
        }
        else if(c=='A'){int x=rd(),y=rd(),v=rd();add(x,y,n);}
        else {int x=rd(),y=rd();printf("%d\n",query(x,y));}    
    }
}

回复

5 条回复,欢迎继续交流。

正在加载回复...