題意

給你一棵樹，邊有邊權，每經過邊一次，就得支付過路費c[i]，點上面有寶藏，每個點只能拿一次。

問從每個點出發，能夠拿到的最大值是多少？

分析

換根法老祖宗，樹形dp必做經典。一上午都獻給這題了TAT

分兩次dfs進行計算
考慮到從一個點出發的最長路徑。兩種情況
1.去了兒子回來后，從父親出去，走到終點。
2.去了父親回來后，從兒子出去，走到終點。
所以需要分別維護這個點從父親出去回來和不回來的最大價值，以及從兒子出去回來和不回來的最大價值。
設g[u][0/1]表示從兒子出去回來和不回來 f[u][0/1]表示從父親出去回來和不回來
g可以從葉節點往根算，但是f需要注意的是，f走出去的最大值的那條路可能是u本身，所以需要維護次大值。

我自己看0和1會看暈，于是這樣寫dp方程會好很多。
g[u][不回]=max（g[u][不回]，g[u][不回]+g[v][回]-2*w） --->在v的子樹中繞圈圈后，從u出去，此時u出去的結點是初始值 out[u]=u
g[u][不回]=max（g[u][不回]，g[u][回]+g[v][不回]-w） --->在u的子樹中繞圈圈后，從v出去,此時u出去的子節點是v，out[u]=v
g[u][回]+=max(0,g[v][回]-2*w ) --->在u的每個有正價值的子樹中繞圈圈

當g[v][回]<=2*w 從兒子出去回來的最大價值甚至小于單走到兒子的這條邊再回來的花費，不如不走，說明g[u][回]里面沒包含走v的情況
f[v][回]=max(f[v][回]，f[u][回]+g[u][回]-2*w) --->從v到u，然后在u的父親、兒子（不包含v）中繞圈圈后，回到v
f[v][不回]=max(f[v][不回]，f[u][不回]+g[u][回]-w) --->從v到u,在u的兒子（不包含v）中繞圈圈后，從u的父親繞圈圈并走到終點
當g[v][回]>2*w
f[v][回]=max(f[v][回]，f[u][回]+g[u][回]-g[v][回]) --->從v到u，然后在u的父親、兒子（包含v）中繞圈圈后，回到v
f[v][不回]=max(f[v][不回]，f[u][不回]+g[u][回]-g[v][回]+w) --->從v到u,在u的兒子（包含v）中繞圈圈后，從u的父親繞圈圈并走到終點

有沒有發現上面的不回中只有從u的父親走到終點，那為什么不可以繞完過后從u的兒子走向終點呢？
其實是可以的，但是這時候你就需要考慮v是不是g[u][不回]的走出去的那個子樹呢？
如果是，說明v這個點自己到兒子的價值已經算過了，
枚舉u的每個兒子不是v的兒子vk，u和vk間的距離為wk
令tmp=tep=val[u]，然后用每個vk更新tmp和tep
tmp=max（tmp，tmp+g[vk][回]-2*wk）
tmp=max（tmp，tep+g[vk][不回]-wk）
tep+=max(0，g[vk][回]-2*wk)
有沒有發現這和第一次dfs計算方式很相似？請翻上去類比一下。tmp其實是g[u][不回]的次大值，tep是g[u][回]的次大值。
最后，枚舉完所有vk后
f[v][不回]=max(f[v][不回]，f[u][回]+tmp-w) --->從v到u，在u的父親中繞圈圈后，從u（不是v）的兒子走到終點
如果不是，還是分g[u][回]有沒有走v討論
否：f[v][不回]=max(f[v][不回],f[u][回]+g[u][不回]-w) --->從v到u,在u的父親中繞圈圈，從u（不是v）的兒子繞圈圈（不包含v）并走到終點
是：f[v][不回]=max(f[v][不回],f[u][回]+g[u][不回]-g[v][回]+w) --->從v到u,在u的父親中繞圈圈，從u（不是v）的兒子繞圈圈（包含v）并走到終點

最后每個點的答案就是max(g[x][回]+f[x][不回],g[x][不回]+f[x][回])

代碼

#include<bits/stdc++.h> using namespace std; #define N 100010 int t,n,cnt,cas; int out[N],val[N],pre[N],first[N],f[N][2],g[N][2]; struct email {int u,v,w;int nxt; }e[N*4]; inline void add(int u,int v,int w) {e[++cnt].nxt=first[u];first[u]=cnt;e[cnt].u=u;e[cnt].v=v;e[cnt].w=w; }void dfs(int u,int fa) {g[u][0]=g[u][1]=val[u];out[u]=u;pre[u]=fa;for(int i=first[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w;if(v==fa)continue;dfs(v,u);g[u][1]=max(g[u][1],g[u][1]+g[v][0]-2*w);if(g[u][1]<g[u][0]+g[v][1]-w)g[u][1]=g[u][0]+g[v][1]-w,out[u]=v;g[u][0]+=max(0,g[v][0]-2*w);} }void dfs2(int v,int u,int w) {if(g[v][0]<=2*w){f[v][0]=max(f[v][0],f[u][0]+g[u][0]-2*w);f[v][1]=max(f[v][1],f[u][1]+g[u][0]-w);}else{f[v][0]=max(f[v][0],f[u][0]+g[u][0]-g[v][0]);f[v][1]=max(f[v][1],f[u][1]+g[u][0]-g[v][0]+w);}if(out[u]==v){int tmp=val[u],tep=val[u];for(int i=first[u];i;i=e[i].nxt){int vk=e[i].v,wk=e[i].w;if(vk==pre[u]||vk==v)continue;tmp=max(tmp,tmp+g[vk][0]-2*wk);tmp=max(tmp,tep+g[vk][1]-wk);tep+=max(0,g[vk][0]-2*wk);}f[v][1]=max(f[v][1],tmp+f[u][0]-w);}else{if(g[v][0]<=2*w)f[v][1]=max(f[v][1],f[u][0]+g[u][1]-w);else f[v][1]=max(f[v][1],f[u][0]+g[u][1]-g[v][0]+w);}for(int i=first[v];i;i=e[i].nxt)if(e[i].v!=u)dfs2(e[i].v,v,e[i].w); }inline void init() {cnt=0;cas++;memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(first,0,sizeof(first)); }int main() {scanf("%d",&t);while(t--){init();scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&val[i]);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}dfs(1,0);dfs2(1,0,0);printf("Case #%d:\n",cas);for(int i=1;i<=n;i++)printf("%d\n",max(f[i][0]+g[i][1],f[i][1]+g[i][0]));}return 0; }

?

轉載于:https://www.cnblogs.com/NSD-email0820/p/9777993.html

總結

以上是生活随笔為你收集整理的【HDU 5834】Magic boy Bi Luo with his excited tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。