題目

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題目分析代碼

題目

分析

代碼