本文主要是介绍2019杭电多校第八场 HDU 6662 Acesrc and Travel(树形DP换根法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6662
题目大意：有两个家伙在博弈，每个家伙都想让自己减对方的值尽可能大，每人走一步直到走不动，走的图是棵树，求最后结果
题目思路：这题给我最大的教训就是..AC前看题解看思路不要看代码！！！！！！！！这个坏习惯导致我昨天白浪费一晚上，每个人的编码习惯不同，稍复杂的题如果没有作者亲自说可能得琢磨半天，还不如照着自己的想法上去干他，反而会做的更快。以后如果想看更优秀的解法也要等AC后！太浪费时间了！
题目思路的话。如果根是固定的，那就是个大水题，因为根是固定的，所以第一个家伙想让a[i]-b[i]尽可能大，第二个家伙想让它尽可能小(a[i]-b[i]尽可能小等价于b[i]-a[i]尽可能大)，所以在每一层选择自己对自己最有利的就行了。一次dfs解决。
但问题是，这题是个无根树！枚举根就n^2了鸭！所以需要使用换根法，通过一个人为根的情况直接on转移到其他所有点得到其它点为根时的情况。这个转移也是本题的最大难点。
如果单说原理其实非常简单，先按照固定根的做法第一次dfs，然后进行第二次dfs换根，第二次dfs时， 对于当前点来说，要么他的最大值or最小值来自于他的孩子们，要么来自于他的父亲，来自他孩子们的情况在第一次dfs就已经拿到手了，所以只要知道来自他爸的极值是啥，而他爸的极值也就两种情况，一种是通过这小子拿到的，一种是不通过这小子拿到的，如果是通过这小子拿到的，那么这小子就不能再用这个极值了(这是我儿子提供的鸭！走两遍了！)所以就只能退一步拿次大值了，所以通过这个值更新这小子的极值就行。
dp[u][0]表示下一步是先手下得到的最大值，dp[u][1]表示是下一步后手下得到的最小值，dp2[u][0],dp[u][1]放次大值。
然后这题很多很骚的细节。
1、如果爸爸没次大值咋整？
啥时候会没有次大值？中间的点度至少为2，肯定有次大值，叶子当不了爸爸没次大值没事，那么只有一种情况！也就是第一次dfs所固定的根没有次大值！这时候从父亲那边来的值只可能是根的a[i]-b[i]，拿来用就完事(亲测有效)，虽说还是判有没有次大值看着舒服，所以后面完整代码还是放的判有无次大值
2、这个更骚..中间的点的极大值和次大值都是从该点出发到某个根，都是合法的，所以直接更新就完事，但是！！！！！对于叶子来说，自己走到自己得到的极值是不符合要求的鸭！！！！！所以对于叶子的更新需要特判，如果是叶子强制把父亲那里得来的结果给他。
看别人的代码一直觉得贼复杂看不懂，自己写写很多问题就通过思考解决了，以后要多思考，少看别人代码。。
以下是代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 1000010;
const ll MAXM = 1000010;
const ll inf = 1ll<<62;
ll a[MAXN],b[MAXN],ans;
vector<ll>v[MAXN];
ll dp[MAXN][2],dp2[MAXN][2];
void dfs(ll u,ll fa){ll len=v[u].size(),num=0;dp[u][0]=dp2[u][0]=-inf;dp[u][1]=dp2[u][1]=inf;rep(i,0,len-1){ll y=v[u][i];if(y==fa)continue;num++;dfs(y,u);if(dp[y][1]+a[u]-b[u]>dp[u][0])dp2[u][0]=dp[u][0],dp[u][0]=dp[y][1]+a[u]-b[u];else if(dp[y][1]+a[u]-b[u]>dp2[u][0])dp2[u][0]=dp[y][1]+a[u]-b[u];if(dp[y][0]+a[u]-b[u]<dp[u][1])dp2[u][1]=dp[u][1],dp[u][1]=dp[y][0]+a[u]-b[u];else if(dp[y][0]+a[u]-b[u]<dp2[u][1])dp2[u][1]=dp[y][0]+a[u]-b[u];}if(!num)dp[u][0]=dp[u][1]=dp2[u][0]=dp2[u][1]=a[u]-b[u];
}
void dfs2(ll u,ll fa){ll len=v[u].size(),num=0;rep(i,0,len-1){ll y=v[u][i];if(y==fa)continue;num++;ll tmp1,tmp2;if(dp2[u][0]==-inf)tmp1=a[u]-b[u]+a[y]-b[y];else{if(dp[y][1]+a[u]-b[u]==dp[u][0]){tmp1=dp2[u][0]+a[y]-b[y];}else tmp1=dp[u][0]+a[y]-b[y];}if(dp2[u][1]==inf)tmp2=a[u]-b[u]+a[y]-b[y];else{if(dp[y][0]+a[u]-b[u]==dp[u][1]){tmp2=dp2[u][1]+a[y]-b[y];}else tmp2=dp[u][1]+a[y]-b[y];}if(v[y].size()==1){dp[y][0]=tmp2,dp[y][1]=tmp1;continue;}if(tmp1<dp[y][1])dp2[y][1]=dp[y][1],dp[y][1]=tmp1;else if(tmp1<dp2[y][1])dp2[y][1]=tmp1;if(tmp2>dp[y][0])dp2[y][0]=dp[y][0],dp[y][0]=tmp2;else if(tmp2>dp2[y][0])dp2[y][0]=tmp2;dfs2(y,u);}
}
int main()
{ll t,n,x,y;scanf("%lld",&t);while(t--){ans=-inf;scanf("%lld",&n);rep(i,1,n)scanf("%lld",&a[i]),v[i].clear();rep(i,1,n)scanf("%lld",&b[i]);rep(i,1,n-1){scanf("%lld%lld",&x,&y);v[x].push_back(y);v[y].push_back(x);}dfs(1,-1);dfs2(1,-1);rep(i,1,n){ans=max(ans,dp[i][1]);}printf("%lld\n",ans);}return 0;
}
/*
999
5
1 2 3 4 5
-1 -2 -3 -4 -5
1 2
2 3
3 4
4 5999
5
2 -1 -3 6 -4
0 0 0 0 0
1 2 1 3 3 4 3 5
*/
这篇关于2019杭电多校第八场 HDU 6662 Acesrc and Travel(树形DP换根法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
