首页 > 代码库 > BZOJ 4034 树上操作(树的欧拉序列+线段树)

BZOJ 4034 树上操作(树的欧拉序列+线段树)

刷个清新的数据结构题爽一爽?

题意:

有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个
操作,分为三种:
操作 1 :把某个节点 x 的点权增加 a 。
操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
 
注意到操作3,询问x到根的路径之间点权和,容易发现这就是欧拉序列中的前缀和。
所以按照树的欧拉序列建线段树,然后操作1就变成单点修改,操作2,就变成了区间内某些点+a,某些点-a,也容易用tag标记进行维护。
 
技术分享
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <bitset>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 100000000
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
    int x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}
    return x*f;
}
const int N=100005;
//Code begin...

struct Seg{LL sum, tag; int p;}seg[N<<4];
struct Edge{int p, next;}edge[N<<1];
int head[N], cnt=1, node[N], pos, fdfs[N][2];
struct DFN{int id; bool flag;}dfn[N<<1];

void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;}
void dfs(int x, int fa){
    dfn[++pos].id=x; dfn[pos].flag=true; fdfs[x][0]=pos;
    for (int i=head[x]; i; i=edge[i].next) {
        int v=edge[i].p;
        if (v==fa) continue;
        dfs(v,x);
    }
    dfn[++pos].id=x; dfn[pos].flag=false; fdfs[x][1]=pos;
}
void push_up(int p){seg[p].p=seg[p<<1].p+seg[p<<1|1].p; seg[p].sum=seg[p<<1].sum+seg[p<<1|1].sum;}
void push_down(int p, int L){
    if (!seg[p].tag) return ;
    seg[p].sum+=(LL)(2*seg[p].p-L)*seg[p].tag;
    seg[p<<1].tag+=seg[p].tag; seg[p<<1|1].tag+=seg[p].tag; seg[p].tag=0;
}
void init(int p, int l, int r){
    if (l<r) {
        int mid=(l+r)>>1;
        init(lch); init(rch); push_up(p);
    }
    else {
        seg[p].sum=dfn[l].flag?node[dfn[l].id]:-node[dfn[l].id];
        seg[p].p=dfn[l].flag;
    }
}
LL query(int p, int l, int r, int R){
    push_down(p,r-l+1);
    if (R<l) return 0;
    if (R>=r) return seg[p].sum;
    int mid=(l+r)>>1;
    return query(lch,R)+query(rch,R);
}
void update1(int p, int l, int r, int X, int val){
    push_down(p,r-l+1);
    if (X<l||X>r) return ;
    if (X==l&&X==r) seg[p].sum+=val;
    else {
        int mid=(l+r)>>1;
        update1(lch,X,val); update1(rch,X,val); push_up(p);
    }
}
void update2(int p, int l, int r, int L, int R, int val){
    push_down(p,r-l+1);
    if (L>r||R<l) return ;
    if (L<=l&&R>=r) seg[p].tag+=val, push_down(p,r-l+1);
    else {
        int mid=(l+r)>>1;
        update2(lch,L,R,val); update2(rch,L,R,val); push_up(p);
    }
}
int main ()
{
    int n, m, flag, u, v;
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d",node+i);
    FO(i,1,n) scanf("%d%d",&u,&v), add_edge(u,v), add_edge(v,u);
    dfs(1,0);
    init(1,1,n<<1);
    while (m--) {
        scanf("%d%d",&flag,&u);
        if (flag==3) printf("%lld\n",query(1,1,n<<1,fdfs[u][0]));
        else {
            scanf("%d",&v);
            if (flag==1) update1(1,1,n<<1,fdfs[u][0],v), update1(1,1,n<<1,fdfs[u][1],-v);
            else update2(1,1,n<<1,fdfs[u][0],fdfs[u][1],v);
        }
    }
    return 0;
}
View Code

 

BZOJ 4034 树上操作(树的欧拉序列+线段树)