題目大意：給你一棵樹，每個(gè)節(jié)點(diǎn)有一個(gè)權(quán)值，Alice和Bob進(jìn)行博弈，起點(diǎn)由Alice確定，確定后交替選擇下一個(gè)點(diǎn)，Alice目標(biāo)是最終值盡可能大，Bob目標(biāo)是盡可能小

題解：很明顯是樹形DP，那么考慮如何dp

設(shè)F[i][0/1]表示第i個(gè)點(diǎn)先手選/后手選的答案

那么不難想到

F[i][0]=max(F[j][1])+v[i]

F[i][1]=min(F[j][0])+v[i]

一次以1為根進(jìn)行dfs可以求出選擇1為根時(shí)的答案，此時(shí)考慮換根

換根時(shí)將換根前的所有狀態(tài)保存下來，dfs下去之后求出其子樹答案后將狀態(tài)復(fù)原

換根時(shí)有兩種情況，1、原根的答案是新根推過來的。2、原根的答案不是從新根推過來的

對(duì)于第二種情況很簡(jiǎn)單，我們只需要把原根當(dāng)做新根的子樹然后進(jìn)行轉(zhuǎn)移即可

考慮第一種情況，將原根變?yōu)閮鹤又?#xff0c;其F值由除新根之外的所有兒子轉(zhuǎn)移而來

于是很容易想到在原有保存最大值（最小值）的基礎(chǔ)上再保存次大值（次小值），這樣就可以O(shè)(1)更新原根的答案了

更新完后就和第二種情況一樣了

代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #define ll long long #define INF 1e18 using namespace std; int T,n; ll v[100001],f[100001][2]; ll mx[100001][2],mn[100001][2]; ll ans; int mxbh[100001],mnbh[100001]; struct node {int x,y; }tr[100001*2]; int hd[100001],nxt[100001*2],rn; void build(int x,int y){tr[++rn]=(node){x,y};nxt[rn]=hd[x];hd[x]=rn;} void init() {rn=0;memset(f,0,sizeof(f));memset(hd,0,sizeof(hd));memset(nxt,0,sizeof(nxt)); } void dfs(int now,int last) {int t1=hd[now],t2;mx[now][0]=mx[now][1]=-INF;mn[now][0]=mn[now][1]=INF;mxbh[now]=0;mnbh[now]=0;while(t1){t2=tr[t1].y;if(t2!=last){dfs(t2,now);if(f[t2][1]>=mx[now][0]){mx[now][1]=mx[now][0];mx[now][0]=f[t2][1];mxbh[now]=t2;}else if(f[t2][1]>mx[now][1])mx[now][1]=f[t2][1];if(f[t2][0]<=mn[now][0]){mn[now][1]=mn[now][0];mn[now][0]=f[t2][0];mnbh[now]=t2;}else if(f[t2][0]<mn[now][1])mn[now][1]=f[t2][0];}t1=nxt[t1];}if(mx[now][0]==-INF)mx[now][0]=0;if(mn[now][0]==INF)mn[now][0]=0;//printf("%d:%lld %lld %lld\n",now,mx[now][0],mn[now][0],v[now]);f[now][0]=mx[now][0]+v[now];f[now][1]=mn[now][0]+v[now];//printf("%d %lld %lld %lld\n",now,f[now][1],max1,v[now]); } void dfs2(int now,int last) {ans=max(ans,f[now][1]);//printf(" %d\n",now);//for(int i=1;i<=n;i++)printf("%lld %lld:%d %d\n",f[i][0],f[i][1],mxbh[i],mnbh[i]);//printf(" %lld %lld|%lld %lld\n",mx[now][0],mx[now][1],mn[now][0],mn[now][1]);//printf("\n");int t1=hd[now],t2;ll fi0,fi1,fj0,fj1,tv,mxj0,mxj1,mnj0,mnj1;int mxbhi,mxbhj,mnbhi,mnbhj;while(t1){t2=tr[t1].y;if(t2!=last){fi0=f[now][0];fi1=f[now][1];fj0=f[t2][0];fj1=f[t2][1];mxbhi=mxbh[now];mnbhi=mnbh[now];mxbhj=mxbh[t2];mnbhj=mnbh[t2];if(mxbh[now]==t2){tv=v[now];if(mx[now][1]!=-INF)tv+=mx[now][1];f[now][0]=tv;}if(mnbh[now]==t2){tv=v[now];if(mn[now][1]!=INF)tv+=mn[now][1];f[now][1]=tv;}mxj0=mx[t2][0];mxj1=mx[t2][1];mnj0=mn[t2][0];mnj1=mn[t2][1];if(mxbhj==0)mx[t2][0]=-INF;if(mnbhj==0)mn[t2][0]=INF;if(f[now][1]>=mx[t2][0]){mx[t2][1]=mx[t2][0];mx[t2][0]=f[now][1];mxbh[t2]=now;}else if(f[now][1]>mx[t2][1])mx[t2][1]=f[now][1];if(f[now][0]<=mn[t2][0]){mn[t2][1]=mn[t2][0];mn[t2][0]=f[now][0];mnbh[t2]=now;}else if(f[now][0]<mn[t2][1])mn[t2][1]=f[now][0];f[t2][0]=mx[t2][0]+v[t2];f[t2][1]=mn[t2][0]+v[t2];dfs2(t2,now);f[now][0]=fi0;f[now][1]=fi1;f[t2][0]=fj0;f[t2][1]=fj1;mx[t2][0]=mxj0;mx[t2][1]=mxj1;mn[t2][0]=mnj0;mn[t2][1]=mnj1;mxbh[now]=mxbhi;mnbh[now]=mnbhi;mxbh[t2]=mxbhj;mnbh[t2]=mnbhj;}t1=nxt[t1];} } int main() {scanf("%d",&T);int a,b;while(T--){init();scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&v[i]);for(int i=1;i<=n;i++){scanf("%d",&a);v[i]-=a;}for(int i=1;i<n;i++){scanf("%d%d",&a,&b);build(a,b);build(b,a);}memset(f,0,sizeof(f));dfs(1,0);ans=-INF;//for(int i=1;i<=n;i++)printf("%lld %lld/%lld %lld:%d %d %lld %lld\n",mx[i][0],mx[i][1],mn[i][0],mn[i][1],mxbh[i],mnbh[i],f[i][0],f[i][1]);dfs2(1,0);//ans=-INF;//for(int i=1;i<=n;i++)ans=max(ans,f[i][1]);//for(int i=1;i<=n;i++)printf("%lld %lld:%d %d\n",f[i][0],f[i][1],mxbh[i],mnbh[i]);printf("%lld\n",ans);}return 0; }

心得：典型的樹形DP的題目，換根時(shí)的操作還需要更多練習(xí)熟練

轉(zhuǎn)載于:https://www.cnblogs.com/worcher/p/11353849.html

總結(jié)

以上是生活随笔為你收集整理的【HDU6662】Acesrc and Travel【树形DP】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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