HDU.5692 Snacks ( DFS序 线段树维护最大值 )

题意分析

给出一颗树，节点标号为0-n，每个节点有一定权值，并且规定0号为根节点。有两种操作：操作一为询问，给出一个节点x,求从0号节点开始到x节点，所能经过的路径的权值最大为多少；操作二为修改，给出一个节点x和值val，将x的权值改为val.

可以看出是树上修改问题。考虑的解题方式有DFS序+线段树，树链剖分，CXTree。由于后两种目前还不会，选择用DFS序来解决。

首先对树求DFS序，在求解过程当中，顺便求解树上前缀和(prefix数组)，并保存从树上节点到DFS序的hash值(hashbcak数组)，然后根据这两个数组来讲建树。

之后查询和修改时，根据已经求得的dfs序，定位到对应区间来修改即可。

注意线段树的权值域、lazy域等保存节点权值的数据以及线段树的查询，修改权值的时候，要用__int64.

在求区间最大值的时候，不要无脑递归子树，要分开求解，长个心眼。

代码总览

#include <bits/stdc++.h>

#define nmax 200005

#define ll __int64

using namespace std;

struct edge{

    int to;

    int next;

}edg[nmax<<1];

struct tree{

    int l,r;

    ll lazy,val;

    int mid(){

        return (l+r)>>1;

    }

}tree[nmax<<2];

int head[nmax],tot,times,in[nmax],out[nmax],hashback[nmax];

ll prefix[nmax],snake[nmax];

void add(int u, int v){

    edg[tot].to = v;

    edg[tot].next = head[u];

    head[u] = tot++;

}

void init(){

    memset(head,-1,sizeof head);

    memset(tree,0,sizeof tree);

    memset(edg,0,sizeof edg);

    memset(snake,0,sizeof snake);

    memset(prefix,0,sizeof prefix);

    memset(hashback,0,sizeof hashback);

    tot = 0;

    times = 0;

}

void dfs(int rt, int f){

    times++;

    in[rt] = times;

    prefix[rt] = snake[rt]+prefix[f];

    hashback[times] = rt;

    for(int i = head[rt]; i!=-1; i = edg[i].next){

        int nxt = edg[i].to;

        if(nxt != f){

            dfs(nxt,rt);

        }

    }

    out[rt]  = times;

}

void PushUp(int rt)

{

    tree[rt].val = max(tree[rt<<1].val , tree[rt<<1|1].val);

}

void PushDown(int rt)

{

    if(tree[rt].lazy){

        tree[rt<<1].lazy += tree[rt].lazy;

        tree[rt<<1|1].lazy += tree[rt].lazy;

        tree[rt<<1].val += tree[rt].lazy;

        tree[rt<<1|1].val +=tree[rt].lazy;

        tree[rt].lazy = 0;

    }

}

void Build(int l, int r, int rt){

    tree[rt].l = l; tree[rt].r = r;

    tree[rt].val = tree[rt].lazy = 0;

    if(l == r){

        tree[rt].val = prefix[hashback[l]];

        return;

    }

    Build(l,tree[rt].mid(),rt<<1);

    Build(tree[rt].mid()+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdateInterval(ll val, int l, int r, int rt){

    if(tree[rt].l >r || tree[rt].r < l) return;

    if(tree[rt].l >= l && tree[rt].r <= r){

        tree[rt].val += val ;

        tree[rt].lazy += val;

        return;

    }

    PushDown(rt);

    UpdateInterval(val,l,r,rt<<1) ;

    UpdateInterval(val,l,r,rt<<1|1);

    PushUp(rt);

}

ll Query(int l,int r,int rt){

    if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].val;

    PushDown(rt);

    ll ans = -1e18;

    if(l <= tree[rt].mid()) ans = max(ans,Query(l,r,rt<<1));

    if(r > tree[rt].mid()) ans = max(ans,Query(l,r,rt<<1|1));

    return ans;

}

int t,n,m;

int main(){

    scanf("%d",&t);

    for(int kase = 1;kase<=t;kase++){

        printf("Case #%d:\n",kase);

        init();

        scanf("%d %d",&n,&m);

        int u,v,x,op;

        ll val;

        for(int i = 0;i<n-1;++i){

            scanf("%d %d",&u,&v);

            u++,v++;

            add(u,v),add(v,u);

        }

        for(int i = 1;i<=n;++i) scanf("%I64d",&snake[i]);

        prefix[0] = 0;

        dfs(1,0);

        Build(1,times,1);

        for(int i = 0;i<m;++i){

            scanf("%d",&op);

            if(op == 1){

                scanf("%d",&x);

                x++;

                printf("%I64d\n",Query(in[x],out[x],1));

            }else{

                scanf("%d %I64d",&x,&val);

                x++;

                ll change = val - snake[x];

                UpdateInterval(change,in[x],out[x],1);

                snake[x] = val;

            }

        }

    }

    return 0;

}