题目

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

Output

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

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

Sample Input

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

分析

根据题意，就是动态维护以当前点为根的子树内的点的深度的最大值，求出dfs序用线段树维护即可。

代码

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 100000
int n,st[MAXN+],ed[MAXN+],dcnt,rdfn[MAXN+],wt[MAXN+],m,T;
long long dep[MAXN+];
template<class T>
void Read(T &x){
    char c;
    bool f=;
    while(c=getchar(),c!=EOF){
        if(c=='-')
            f=;
        if(c>='0'&&c<='9'){
            x=c-'0';
            while(c=getchar(),c>='0'&&c<='9')
                x=x*+c-'0';
            ungetc(c,stdin);
            if(f)
                x=-x;
            return;
        }
    }
}
struct node{
    int v;
    node *next;
}*adj[MAXN+],edge[MAXN*+],*ecnt=edge;
inline void addedge(int u,int v){
    node *p=++ecnt;
    p->v=v;
    p->next=adj[u];
    adj[u]=p;
}
namespace SegmentTree{
struct node{
    long long mx,tag;
}tree[MAXN*+];
inline void update(int i){
    tree[i].mx=max(tree[i<<].mx,tree[(i<<)|].mx);
}
inline void push_down(int i){
    if(tree[i].tag){
        tree[i<<].mx+=tree[i].tag,tree[i<<].tag+=tree[i].tag;
        tree[(i<<)|].mx+=tree[i].tag,tree[(i<<)|].tag+=tree[i].tag;
        tree[i].tag=;
    }
}
void insert(int i,int l,int r,int ll,int rr,int d){
    if(ll<=l&&r<=rr){
        tree[i].tag+=d;
        tree[i].mx+=d;
        return;
    }
    if(ll>r||rr<l)
        return;
    push_down(i);
    int mid=(l+r)>>;
    insert(i<<,l,mid,ll,rr,d);
    insert((i<<)|,mid+,r,ll,rr,d);
    update(i);
}
long long get_mx(int i,int l,int r,int ll,int rr){
    if(ll<=l&&r<=rr)
        return tree[i].mx;
    if(ll>r||rr<l)
        return ll;
    push_down(i);
    int mid=(l+r)>>;
    return max(get_mx(i<<,l,mid,ll,rr),get_mx((i<<)|,mid+,r,ll,rr));
}
void build(int i,int l,int r){
    tree[i].tag=;
    if(l==r){
        tree[i].mx=dep[rdfn[l]];
        return;
    }
    int mid=(l+r)>>;
    build(i<<,l,mid);
    build((i<<)|,mid+,r);
    update(i);
}
}
void dfs(int u,int fa){
    st[u]=++dcnt;
    dep[u]=dep[fa]+wt[u];
    rdfn[dcnt]=u;
    for(node *p=adj[u];p;p=p->next)
        if(p->v!=fa)
            dfs(p->v,u);
    ed[u]=dcnt;
}
using namespace SegmentTree;
void read(){
    Read(n),Read(m);
    int i,u,v;
    for(i=;i<n;i++){
        Read(u),Read(v);
        addedge(u,v);
        addedge(v,u);
    }
    for(i=;i<n;i++)
        Read(wt[i]);
}
void solve(){
    dep[]=;
    dfs(,);
    build(,,n);
    int p,x,y;
    while(m--){
        Read(p);
        if(!p){
            Read(x),Read(y);
            insert(,,n,st[x],ed[x],y-wt[x]);
            wt[x]=y;
        }
        else{
            Read(x);
            printf("%I64d\n",get_mx(,,n,st[x],ed[x]));
        }
    }
}
int main()
{
    Read(T);
    int cnt=;
    while(T--){
        dcnt=;
        printf("Case #%d:\n",++cnt);
        memset(adj,,sizeof adj);
        ecnt=edge;
        read();
        solve();
    }
}

转载于:https://www.cnblogs.com/outerform/p/5921833.html

【图论+线段树】[2016"百度之星" - 初赛(Astar Round2A)]Snacks题目分析代码

题目

分析

代码