題目鏈接：點擊查看

題目大意：中文題目，不多贅述

題目分析：因為要求路線上權(quán)值和最大，我們可以用前綴和的思想來儲存，故我們需要來維護最大值，可以用線段樹來維護最大值，若想用線段樹的話，前提必須是線性區(qū)間，所以我們將樹用dfs序轉(zhuǎn)換成線性區(qū)間，然后就可以用線段樹來維護最大值了。

注意，這個題有個坑點，因為最大值已經(jīng)爆int了，所以inf要設(shè)成1e18，因為這個調(diào)了一整天。。。自閉

上代碼吧，這次注釋寫的超全，因為中途讓學(xué)長幫忙找bug，所以特意將注釋寫的超詳細

#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const LL inf=1e18;const int N=1e5+100;vector<int>node[N];LL vv[N],v[N];// vv:權(quán)值和，類似于前綴和，v:點權(quán)值 int L[N],R[N];//儲存每個點dfs序后的子樹的線性區(qū)間段， [L,R]閉區(qū)間 int cnt;//輔助記錄序號 void dfs(int u,int fa,LL value)// value變量維護前綴和，每次向下遞歸的時候維護鏈上的前綴和 {L[u]=++cnt;//儲存起點 vv[cnt]=value;for(int i=0;i<node[u].size();i++){if(node[u][i]==fa)continue;dfs(node[u][i],u,value+v[node[u][i]]);}R[u]=cnt;//儲存終點 }struct Node//維護最大值的線段樹，維護類似于權(quán)值和的最大值 {int l,r;LL mmax;//最大值 LL lazy;//懶標記 }tree[N<<2];void pushup(int k)//上傳函數(shù) {tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); }void pushdown(int k)//下傳函數(shù) {tree[k<<1].mmax+=tree[k].lazy;//更新值 tree[k<<1|1].mmax+=tree[k].lazy;tree[k<<1].lazy+=tree[k].lazy;//更新懶標記 tree[k<<1|1].lazy+=tree[k].lazy;tree[k].lazy=0;//清空懶標記 }void build(int k,int l,int r)//建樹 {tree[k].l=l;tree[k].r=r;tree[k].lazy=0;//初始化賦值 if(l==r)//相等更新葉子 {tree[k].mmax=vv[l];return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);//上傳更新 }void update(int k,int l,int r,LL val)//更新函數(shù) {if(tree[k].r<l||tree[k].l>r)//區(qū)間外的返回 return;if(tree[k].r<=r&&tree[k].l>=l)//區(qū)間內(nèi)的更新 {tree[k].lazy+=val;tree[k].mmax+=val;return;}if(tree[k].lazy)//標記下傳 pushdown(k);update(k<<1,l,r,val);//更新左區(qū)間 update(k<<1|1,l,r,val);//更新右區(qū)間 pushup(k);//上傳更新 }LL query(int k,int l,int r)//查詢函數(shù) {if(tree[k].r<l||tree[k].l>r)//不符合條件返回?zé)o窮小 return -inf;if(tree[k].r<=r&&tree[k].l>=l)//符合條件返回最大值 return tree[k].mmax;if(tree[k].lazy)//下傳標記 pushdown(k);return max(query(k<<1,l,r),query(k<<1|1,l,r));//最后符合條件中的最大值 }int main() { // freopen("input.txt","r",stdin)int w;cin>>w;int kase=0;while(w--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)// vector存邊 node[i].clear();for(int i=1;i<n;i++)//因為習(xí)慣原因，我將點全部右移一個單位，改成了從1~n {int u,v;scanf("%d%d",&u,&v);node[u+1].push_back(v+1);//右移 node[v+1].push_back(u+1);}for(int i=1;i<=n;i++)//存點權(quán) scanf("%lld",v+i);cnt=0;//從1開始 ：因為一開始是++cnt，所以cnt初始化為0 dfs(1,-1,v[1]);//dfs序 build(1,1,n);//建樹 printf("Case #%d:\n",++kase);while(m--)//m次操作 {int op;scanf("%d",&op);if(op==1)//查詢 {int x;scanf("%d",&x);printf("%lld\n",query(1,L[x+1],R[x+1]));}else//更新 {int x;LL y;scanf("%d%lld",&x,&y);update(1,L[x+1],R[x+1],y-v[x+1]);v[x+1]=y;}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5692 Snacks(dfs序+线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。