M_sea

洛谷3178 [HAOI2015]树上操作
Luogu分析显然是树链剖分。线段树要资瓷区间加和区间求和。还要开long long。代码#include <...
扫描右侧二维码阅读全文
31
2018/10

洛谷3178 [HAOI2015]树上操作

Luogu

分析

显然是树链剖分。

线段树要资瓷区间加和区间求和。

还要开long long。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100010;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m;
int a[MAXN];

int dep[MAXN],sz[MAXN],fa[MAXN],hson[MAXN];

inline void Dfs1(int u,int f) {
    fa[u]=f,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==f) continue;
        dep[v]=dep[u]+1;
        Dfs1(v,u);
        sz[u]+=sz[v];
        if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
    }
}

int tot=0;
int top[MAXN],id[MAXN],real[MAXN];

inline void Dfs2(int u,int anc) {
    top[u]=anc,id[u]=++tot,real[tot]=u;
    if (!hson[u]) return;
    Dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa[u]||v==hson[u]) continue;
        Dfs2(v,v);
    }
}

struct Segment_Tree {
    int sumv[MAXN<<2],addv[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(int o) { sumv[o]=sumv[lson]+sumv[rson]; }
    inline void pushdown(int o,int l,int r) {
        if (addv[o]) {
            int mid=(l+r)>>1;
            addv[lson]+=addv[o],addv[rson]+=addv[o];
            sumv[lson]+=(mid-l+1)*addv[o];
            sumv[rson]+=(r-mid)*addv[o];
            addv[o]=0;
        }
    }
    inline void build(int o,int l,int r) {
        if (l==r) { sumv[o]=a[real[l]]; return; }
        int mid=(l+r)>>1;
        build(lson,l,mid);
        build(rson,mid+1,r);
        pushup(o);
    }
    inline void update(int o,int l,int r,int ql,int qr,int v) {
        if (ql<=l&&r<=qr) { sumv[o]+=v*(r-l+1); addv[o]+=v; return; }
        pushdown(o,l,r);
        int mid=(l+r)>>1;
        if (ql<=mid) update(lson,l,mid,ql,qr,v);
        if (qr>mid) update(rson,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sumv[o];
        pushdown(o,l,r);
        int mid=(l+r)>>1,rt=0;
        if (ql<=mid) rt+=query(lson,l,mid,ql,qr);
        if (qr>mid) rt+=query(rson,mid+1,r,ql,qr);
        pushup(o);
        return rt;
    }
};

Segment_Tree T;

inline void node_add(int u,int v) { T.update(1,1,n,id[u],id[u],v); }
inline void tree_add(int u,int v) { T.update(1,1,n,id[u],id[u]+sz[u]-1,v); }
inline int chain_query(int u,int v) {
    int tu=top[u],tv=top[v],rt=0;
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); }
        rt+=T.query(1,1,n,id[tu],id[u]);
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    rt+=T.query(1,1,n,id[v],id[u]);
    return rt;
}

mainint main() {
    n=read(),m=read();
    for (re int i=1;i<=n;i++) a[i]=read();
    for (re int i=1,u,v;i<n;i++) {
        u=read(),v=read();
        addEdge(u,v); addEdge(v,u);
    }
    dep[1]=1; Dfs1(1,0); Dfs2(1,1); T.build(1,1,n);
    while (m--) {
        int op=read(),x,y;
        if (op==1) { x=read(),y=read(); node_add(x,y); }
        if (op==2) { x=read(),y=read(); tree_add(x,y); }
        if (op==3) { x=read(); printf("%lld\n",chain_query(1,x)); }
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 03 PM

发表评论