Snacks

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

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

Source

2016"百度之星" - 初赛（Astar Round2A）

百度之星初赛的时候当时没做出来,现在练习DFS序,知道是线段树+dfs序感觉就容易了,都是套路,感觉非常厉害的题目.

利用dfs序将树转换成了线段树.我们保存一个从根节点到每个子节点的前缀和,所以将其转换成线段树之后就对于原来的某个结点,其最大值就是从0到它+它到它的所有子结点中最大的那一个。转换成线段树之后直接进行区间查找,然后每次改变其值也只需要成段更新即可..但是成段更新不能够更新到叶子结点,那样会超时,所以只能更新到段为止,所以要加Pushdown操作.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long  LL;

const int N =;

const LL INF = 1e18;

struct Edge{

    int v,next;

}edge[N<<];

int head[N],tot,cnt;

int in[N],out[N];

LL lazy[N<<];

LL sum[N<<],cost[N]; ///sum 存前缀和

LL dis[N],b[N];

int n,q;

void init(){

    memset(head,-,sizeof(head));

    tot = cnt = ;

}

void addEdge(int u,int v,int &k){

    edge[k].v = v,edge[k].next = head[u],head[u] = k++;

}

void dfs(int u,int pre){

    in[u] = ++cnt;

    b[cnt] = dis[u]; ///原来的树的下标对应线段树的下标

    for(int k=head[u];k!=-;k=edge[k].next){

        int v = edge[k].v;

        if(v==pre) continue;

        dis[v] = dis[u] + cost[v];

        dfs(v,u);

    }

    out[u] = cnt;

}

void pushup(int idx){

    sum[idx] = max(sum[idx<<],sum[idx<<|]);

}

void pushdown(int idx)

{

    if(lazy[idx])

    {

        sum[idx << ] += lazy[idx];

        sum[idx <<  | ] += lazy[idx];

        lazy[idx << ] += lazy[idx];

        lazy[idx <<  | ] += lazy[idx];

        lazy[idx] = ;

    }

    return;

}

void build(int l,int r,int idx){

    lazy[idx] = ;

    if(l==r){

        sum[idx] =  b[l];

        return ;

    }

    int mid = (l+r)>>;

    build(l,mid,idx<<);

    build(mid+,r,idx<<|);

    pushup(idx);

}

void update(int l,int r,int L,int R,int idx,int val){

    if(l>=L&&r<=R){

        sum[idx] =sum[idx] + val;

        lazy[idx] =lazy[idx] + val;

        return;

    }

    int mid = (l+r)>>;

    pushdown(idx);

    if(mid>=L) update(l,mid,L,R,idx<<,val);

    if(mid<R)  update(mid+,r,L,R,idx<<|,val);

    pushup(idx);

}

LL MAX = -;

void query(int l,int r,int L,int R,int idx){

    if(l >= L&& r <= R){

        MAX = max(MAX,sum[idx]);

        return ;

    }

    int mid = (l+r)>>;

    pushdown(idx);

    if(mid>=L)  query(l,mid,L,R,idx<<);

    if(mid<R)   query(mid+,r,L,R,idx<<|);

}

int main()

{

    int tcase,t=;

    scanf("%d",&tcase);

    while(tcase--){

        init();

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

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

            int u,v;

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

            addEdge(u,v,tot);

            addEdge(v,u,tot);

        }

        for(int i=;i<n;i++){

            scanf("%lld",&cost[i]);

        }

        dis[] = cost[];

        dfs(,-);

        build(,n,);

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

        while(q--){

            int opr ,x, y;

            scanf("%d",&opr);

            if(opr==){

                scanf("%d",&x);

                MAX = -INF;

                query(,n,in[x],out[x],);

                printf("%lld\n",MAX);

            }

            else{

                scanf("%d%d",&x,&y);

                LL change = (LL)y-cost[x];  ///这里累加变化量

                update(,n,in[x],out[x],,change);

                cost[x] = y;

            }

        }

    }

    return ;

}

巴特西

hdu 5692(dfs序+线段树,好题)

Snacks

最新文章

热门文章