HDU 5692 - Snacks - [DFS序+線段樹]

題目連結：​​http://acm.hdu.edu.cn/showproblem.php?pid=5692​​

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

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 5

Sample Output

Case #1:

102

27

2

20

題解：

題目給出n個點和n-1條邊，并且是連通圖，那麼顯然是一棵樹；

一棵無向樹，我們可以任意取一個節點作為樹根，根據題意取編号為0的節點為樹根；

那麼，對于其他的1~n-1号節點，從樹根（0号節點）到它們隻有唯一一條路徑，

假設sum[i]代表從0号節點到i号節點這條路徑上所有的點（包括節點0和i）的value值之和；

（換句話說，假設從root=0，到i節點的唯一一條簡單路徑為0-1-3-5-i，那麼 sum[i] = value[0] + value[1] + value[3] + value[5] + value[i]；）

then，對于題目中描述的兩種操作：

①修改節點i的value[i]值：

　　一旦修改value[i]，會影響到以i為樹根的子樹内的所有節點的sum[]，

　　假設value[i]+=k，那麼其正科統領的一整棵子樹上的節點上的sum[]都要加上k；

②查詢：從0号節點出發，經過節點x，走一條簡單路徑，所經過的所有節點的value值之和的最大值：

　　顯然，這就是枚舉節點x統領的子樹上所有的節點的sum[]值，找到其中最大的就行；

（注：在上面，節點x統領的子樹内所有的點，包含節點x自己）

那麼，如果我們使用DFS序把整棵樹“拍平”，把他們排列到一串序列中……

這個序列中，節點x的in[x]和out[x]代表：[ in[x] , out[x] ]區間内的點正好是節點x統領的子樹内的所有節點；

那麼對于上面兩種操作，我們從可以從“樹上修改，樹上查詢”變成“區間修改，區間查詢”……

即：

　　①x節點統領的子樹内，所有節點的sum[]+=k　→　[ in[x] , out[x] ]區間内所有節點的sum[]+=k；

　　②x節點統領的子樹内，查詢所有節點中sum[]的最大值　→　查詢[ in[x] , out[x] ]區間内所有節點的sum[]最大值；

顯然，如果使用線段樹進行維護，兩種操作就都從O(n)時間複雜度變成了O(lgn)的時間複雜度；

AC代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn=100000+5;
const LL INF=1e18;

int n,m;
LL val[maxn],sum[maxn];

//鄰接表-st
struct Edge{
    int u,v;
    Edge(int u,int v){this->u=u,this->v=v;}
};
vector<Edge> E;
vector<int> G[maxn];
void Adjacency_List_Init(int l,int r)
{
    E.clear();
    for(int i=l;i<=r;i++) G[i].clear();
}
void addedge(int u,int v)
{
    E.push_back(Edge(u,v));
    E.push_back(Edge(v,u));
    int _size=E.size();
    G[u].push_back(_size-2);
    G[v].push_back(_size-1);
}
//鄰接表-ed

//dfs序-st
int dfs_clock;
bool vis[maxn];
int in[maxn],out[maxn];
int peg[maxn];
inline void DFS_Init()
{
    dfs_clock=0;
    memset(vis,0,sizeof(vis));
}
void dfs(int now)
{
    in[now]=++dfs_clock;
    peg[in[now]]=now;

    vis[now]=1;
    for(int i=0,_size=G[now].size();i<_size;i++)
    {
        int nxt=E[G[now][i]].v;
        if(!vis[nxt])
        {
            sum[nxt]=sum[now]+val[nxt];
            dfs(nxt);
        }
    }

    out[now]=dfs_clock;
}
//dfs序-ed

//線段樹-st
struct Node{
    int l,r;
    LL val,lazy;
    void update(LL x)
    {
        val+=x;
        lazy+=x;
    }
}node[4*maxn];
void pushdown(int root)
{
    if(node[root].lazy)
    {
        node[root*2].update(node[root].lazy);
        node[root*2+1].update(node[root].lazy);
        node[root].lazy=0;
    }
}
void pushup(int root)
{
    node[root].val=max(node[root*2].val,node[root*2+1].val);
}
void build(int root,int l,int r)
{
    node[root].l=l; node[root].r=r;
    node[root].val=0; node[root].lazy=0;
    if(l==r) node[root].val=sum[peg[l]];
    else
    {
        int mid=l+(r-l)/2;
        build(root*2,l,mid);
        build(root*2+1,mid+1,r);
        pushup(root);
    }
}
void update(int root,int st,int ed,int val)
{
    if(st>node[root].r || ed<node[root].l) return;
    if(st<=node[root].l && node[root].r<=ed) node[root].update(val);
    else
    {
        pushdown(root);
        update(root*2,st,ed,val);
        update(root*2+1,st,ed,val);
        pushup(root);
    }
}
LL query(int root,int st,int ed)
{
    if(ed<node[root].l || node[root].r<st) return -INF;
    if(st<=node[root].l && node[root].r<=ed) return node[root].val;
    else
    {
        pushdown(root);
        LL lson=query(root*2,st,ed);
        LL rson=query(root*2+1,st,ed);
        pushup(root);
        return max(lson,rson);
    }
}
//線段樹-ed


int main()
{
    int t;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d%d",&n,&m);

        Adjacency_List_Init(0,n-1);
        for(int i=1,u,v;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
        }

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

        DFS_Init();
        sum[0]=val[0];
        dfs(0);

        build(1,1,n);
        printf("Case #%d:\n",kase);
        for(int i=1,type,x,y;i<=m;i++)
        {
            scanf("%d",&type);
            if(type==0)
            {
                scanf("%d%d",&x,&y);
                update(1,in[x],out[x],y-val[x]);
                val[x]=y;
            }
            if(type==1)
            {
                scanf("%d",&x);
                printf("%I64d\n",query(1,in[x],out[x]));
            }
        }
    }
}      

注意：這裡的線段樹，是區間更新（一個區間加上一個值），區間查詢（一個區間的val維護：區間内所有節點最大值）。