Acesrc and Travel(Dp换根)

题目

HDU
题目大意：
$n$ 个点的一棵无根无向树，每个点代表一个景点，有A和B两个人，A先手。每个人轮流选择下一个景点去哪里（选择的景点必须和当前景点有连边），走到第i个景点的时候，A会获得 $a_i$ 点满意度，B会获得 $b_i$点满意度，每个景点只能走一次，当走到无法再走的时候，游戏结束。现在已知A和B都以最佳策略选取景点，最佳策略指的是自己的总满意度和对方的总满意度的差值最大。求这个最大差值。
$1\le n\le 10^5$

思路

首先让1为根
记 $va{l}_u=a_u?b_u$
$f[u][0]$ :u子树内从u开始A先走得到最大差值
$f[u][1]$ :u子树内从u开始B先走得到最小差值
则有转移:
$f[u][0]=min(f[v][1])+va{l}_u$
因为下一步是B走，他会选择最小的
$f[u][1]=max(f[v][0])+va{l}_u$
因为下一步是A走，他会选择最大的
考虑换根
自顶向下的过程中我们更换 $f$ 的定义：
$f[u][0]$: 从u开始A先走得到最大差值
$f[u][1]$: 从u开始B先走得到最小差值
答案就是 $max(f[i][0])$

考虑如何更新 $f$
如图，假设现在的 $f[u]$ 并不是从 $v$ 转移过来的，那么有：
$f[v][0]=min(f[u][1]+val[u],f[v][0])$
$f[v][1]=max(f[u][0]+val[u],f[v][1])$
对应了从 $v$ 往上走和往下走
但是有可能 $f[v][0]$ 本身在第一次就更新了 $u$ 于是我们需要存储转移的次大值，次小值
注意第一次 $Dp$ 时，如果为叶子节点 $f2[u][0],f2[u][1]$ 为对应±INF
当然第二次dp会有特殊情况：

比如现在 $u$ 现在向下并没有次值于是更新 $v$ 时我们就让它的次值为自己的 $val$
还有对叶子计算答案时由于向下并没有选择，于是要强制让它的 $f$ 数组变为向上的即对应 $u$ 数组 $f[u][0]+val[v]$

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<bitset>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
#define MAXN 200000
#define INF (LL)1e18+5
struct Edge{
    int v,nxt;
}edge[2*MAXN+5];
int ecnt,head[MAXN+5];
void Addedge(int u,int v){
    edge[++ecnt]=(Edge){
    v,head[u]},head[u]=ecnt;edge[++ecnt]=(Edge){
    u,head[v]},head[v]=ecnt;return ;
}
int n;
bool leaf[MAXN+5];
LL val[MAXN+5],f[MAXN+5][2],f2[MAXN+5][2],ans;
void DFS1(int u,int fa){
    //0 1 max 2 3 minbool vis=0;for(int i=head[u];i;i=edge[i].nxt){
    int v=edge[i].v;if(v==fa) continue;vis=1,DFS1(v,u);if(f[u][0]>f[v][1]+val[u])f2[u][0]=f[u][0],f[u][0]=f[v][1]+val[u];else if(f2[u][0]>f[v][1]+val[u])f2[u][0]=f[v][1]+val[u];if(f[u][1]<f[v][0]+val[u])f2[u][1]=f[u][1],f[u][1]=f[v][0]+val[u];else if(f2[u][1]<f[v][0]+val[u])f2[u][1]=f[v][0]+val[u];}if(!vis)leaf[u]=1,f[u][0]=f[u][1]=val[u];return ;
}
void DFS2(int u,int fa){
    for(int i=head[u];i;i=edge[i].nxt){
    int v=edge[i].v;if(v==fa) continue;LL Min=(f[v][1]+val[u]==f[u][0]?f2[u][0]:f[u][0]);LL Max=(f[v][0]+val[u]==f[u][1]?f2[u][1]:f[u][1]);if(Max==-INF) Max=val[u];if(Min==INF) Min=val[u];Max+=val[v],Min+=val[v];if(leaf[v])ans=max(ans,Max);if(Max<f[v][0])f2[v][0]=f[v][0],f[v][0]=Max;else if(Max<f2[v][0])f2[v][0]=Max;if(Min>f[v][1])f2[v][1]=f[v][1],f[v][1]=Min;else if(Min>f2[v][1])f2[v][1]=Min;ans=max(ans,f[v][0]);DFS2(v,u);}return ;
}
int main(){
    int T=read();while(T--){
    n=read();for(int i=1;i<=n;i++)f[i][0]=f2[i][0]=INF,f[i][1]=f2[i][1]=-INF,leaf[i]=0;for(int i=1;i<=n;i++)val[i]=read();for(int i=1;i<=n;i++)val[i]-=read();for(int i=1;i<n;i++){
    int u=read(),v=read();Addedge(u,v);}DFS1(1,0);ans=f[1][0];DFS2(1,0);printf("%lld\n",ans);for(int i=1;i<=n;i++)head[i]=0;ecnt=0;}return 0;
}

思考

坑点极多，写死我了，以后换根要多思考数组定义和转移方式简化代码