HDU5692(dfs序+线段树)

Snacks

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1277 Accepted Submission(s): 292

Problem Description
百度科技园内有n个零食机，零食机之间通过n−1条路相互连通。每个零食机都有一个值v，表示为小度熊提供零食的价值。

由于零食被频繁的消耗和补充，零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。

为小度熊规划一个路线，使得路线上的价值总和最大。

Input
输入数据第一行是一个整数T(T≤10)，表示有T组测试数据。

对于每组数据，包含两个整数n,m(1≤n,m≤100000)，表示有n个零食机，m次操作。

接下来n−1行，每行两个整数x和y(0≤x,y<n)，表示编号为x的零食机与编号为y的零食机相连。

接下来一行由n个数组成，表示从编号为0到编号为n−1的零食机的初始价值v(|v|<100000)。

接下来m行，有两种操作：0 x y，表示编号为x的零食机的价值变为y；1 x，表示询问从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。

本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上：

`#pragma comment(linker, "/STACK:1024000000,1024000000") `

Output
对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。

对于每次询问，输出从编号为0的零食机出发，必须经过编号为x零食机的路线中，价值总和的最大值。

Sample Input
1
6 5
0 1
1 2
0 3
3 4
5 3
7 -5 100 20 -5 -7
1 1
1 3
0 2 -1
1 1
1 5

Sample Output
Case #1:
102
27
2
20

思路：用Hash[lch[u]]记录从根节点带u结点所经过结点的权值之和。那么从根节点经过u结点所有路径权值之和的最大值为 max(Hash[lch[u]],..,Hash[rch[u]]);

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=100005;
typedef long long LL;
int n,m;
vector<int> arc[MAXN];
int val[MAXN];

int lch[MAXN],rch[MAXN],key;
LL has[MAXN];
void dfs(int u,int fa)
{
    lch[u]=++key;
    has[lch[u]]=val[u]+has[lch[fa]];
    for(int i=0;i<arc[u].size();i++)
    {
        int to=arc[u][i];
        if(to!=fa)
        {
            dfs(to,u);
        }
    }
    rch[u]=key;
}

struct Node{
    int l,r;
    LL mx,lazy;
}segTree[MAXN*3];
void build(int rt,int l,int r)
{
    segTree[rt].l=l;
    segTree[rt].r=r;
    segTree[rt].lazy=0;
    if(l==r)
    {
        segTree[rt].mx=has[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build((rt<<1)|1,mid+1,r);
    segTree[rt].mx=max(segTree[rt<<1].mx,segTree[(rt<<1)|1].mx);
}

void pushDown(int rt)
{
    if(segTree[rt].lazy!=0)
    {
        segTree[rt<<1].mx+=segTree[rt].lazy;
        segTree[(rt<<1)|1].mx+=segTree[rt].lazy;    
        segTree[rt<<1].lazy+=segTree[rt].lazy;
        segTree[(rt<<1)|1].lazy+=segTree[rt].lazy;
        segTree[rt].lazy=0;
    }
}

void update(int rt,int l,int r,LL value)
{
    if(segTree[rt].l==l&&segTree[rt].r==r)
    {
        segTree[rt].mx+=value;
        segTree[rt].lazy+=value;
        return ;
    }
    pushDown(rt);
    int mid=(segTree[rt].l+segTree[rt].r)>>1;
    if(r<=mid)
    {
        update(rt<<1,l,r,value);
    }
    else if(mid<l)
    {
        update((rt<<1)|1,l,r,value);
    }
    else
    {
        update(rt<<1,l,mid,value);
        update((rt<<1)|1,mid+1,r,value);
    }
    segTree[rt].mx=max(segTree[rt<<1].mx,segTree[(rt<<1)|1].mx);
}

LL query(int rt,int l,int r)
{
    if(segTree[rt].l==l&&segTree[rt].r==r)
    {
        return segTree[rt].mx;
    }
    pushDown(rt);
    int mid=(segTree[rt].l+segTree[rt].r)>>1;
    if(r<=mid)
    {
        return query(rt<<1,l,r);
    }
    else if(mid<l)
    {
        return query((rt<<1)|1,l,r);
    }
    else
    {
        return max(query(rt<<1,l,mid),query((rt<<1)|1,mid+1,r));
    }
    segTree[rt].mx=max(segTree[rt<<1].mx,segTree[(rt<<1)|1].mx);
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        key=0;
        memset(has,0,sizeof(has));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)    arc[i].clear();
        for(int i=0;i<n-1;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            u++;v++;
            arc[u].push_back(v);
            arc[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
        }
        dfs(1,0);
        build(1,1,n);
        printf("Case #%d:
",cas);
        while(m--)
        {
            int type;
            scanf("%d",&type);
            if(type==1)
            {
                int x;
                scanf("%d",&x);
                x++;
                LL res=query(1,lch[x],rch[x]);
                printf("%lld
",res);
            }
            else
            {
                int x,y;
                scanf("%d %d",&x,&y);
                x++;
                update(1,lch[x],rch[x],y-val[x]);
                val[x]=y;//注意更新 
            }
        }
    }
    return 0;
}