大意
给出一颗树，每个点上有一个权值\(A[i]\)，有两个绝顶聪明的人甲和乙。
甲乙两人一起在树上轮流走，不能走之前经过的点。（甲乙时刻在一起）
甲先手，并可以确定起点。甲想要走过的点权之和最大，乙想要权值和最小。
求最终权值和。
思路
首先有个很明显的想法就是树形Dp：
设\(F0[u]\)表示以\(u\)为根的子树内，甲先手，以\(u\)为起点的权值和。
设\(F1[u]\)表示以\(u\)为根的子树内，乙先手，以\(u\)为起点的权值和。
那么转移式就为：
\(F0[u]=Min(F1[v])+A[u]\)
\(F1[u]=Max(F0[v])+A[u]\)
其中\(v\)为\(u\)的一个儿子。
这样我们可以处理出每个点只在其子树范围走内的答案。
考虑从某个点出发，向上走形成的答案。
我们设\(TP[V]\)表示不走\(V\)的子树，甲先手，以\(V\)为起点的权值和。
那么\(TP[V]\)的更新就会有两种情况，一种是先走\(U\)，然后再走\(U\)的某个儿子。
对于这种情况，甲肯定会选\(U\)的儿子中\(F0\)最大的值，即\(F1[U]\)。
但又由于\(V\)可能本身就是最大的，所以应该记录下\(F1\)的最大值与次大值进行转移。
对于另一种，就是先走\(U\)，再走\(Fa\)的情况。
对于这种情况，在走到\(Fa\)时，\(B\)肯定会选择较小的那一边走。
所以就是\(Fa\)所有儿子中最小的\(F1\)，即\(F0[Fa]\)与\(Fa\)向上走的情况\(TP[Fa]\)取较小值就行了。
但同理，\(U\)可能是最小的，所以记录下\(F0\)的最小值与次小值进行转移。
对于以上两种\(TP\)情况的选择由于是\(A\)选，所以取较大值。
注：在转移\(TP\)时，时刻注意为一条链的情况。
最后枚举以哪一个点为起点，取\(F0[U][0]\)与\(TP[U]\)的较小值就行了。
注意叶子节点与根的取值。
代码
细节超多，易错点主要集中在初值的赋值以及根上。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=600005;
const long long INF=1e17;
int K,N,A[MAXN];
int son0[MAXN],son1[MAXN];
long long Ans;
long long F0[MAXN][2],F1[MAXN][2];//0:A|||||||1:B
long long TP[MAXN];
vector<int>P[MAXN];
void DFS(int u,int fa){
int Ok=0;
int size=P[u].size();
for(int i=0;i<size;i++){
int v=P[u][i];
if(v==fa)continue;
DFS(v,u);Ok=1;
if(F1[v][0]+A[u]<F0[u][0])F0[u][1]=F0[u][0],F0[u][0]=min(F0[u][0],F1[v][0]+A[u]),son0[u]=v;
else F0[u][1]=min(F0[u][1],F1[v][0]+A[u]);
if(F0[v][0]+A[u]>F1[u][0])F1[u][1]=F1[u][0],F1[u][0]=max(F1[u][0],F0[v][0]+A[u]),son1[u]=v;
else F1[u][1]=max(F1[u][1],F0[v][0]+A[u]);
}
if(!Ok)F0[u][0]=F0[u][1]=F1[u][0]=F1[u][1]=A[u];
}
void DFS2(int u,int fa){
int size=P[u].size();
for(int i=0;i<size;i++){
int v=P[u][i];
if(v==fa)continue;
long long val1=INF,val2=INF;
if(P[u].size()!=2){
if(son1[u]==v)val1=F1[u][1];
else val1=F1[u][0];
}else val1=u==1?A[u]:-INF;
if(P[fa].size()!=2){
if(son0[fa]==u)val2=F0[fa][1];
else val2=F0[fa][0];
}val2=min(val2,TP[fa]);
TP[v]=A[v]+max(val1,val2+A[u]);
DFS2(v,u);
}
}
int main(){
//freopen("data.txt","r",stdin);
//freopen("mine.txt","w",stdout);
scanf("%d",&K);
while(K--){
scanf("%d",&N);
for(int i=0;i<=N;i++){
F0[i][0]=F0[i][1]=INF;
F1[i][0]=F1[i][1]=-INF;
son0[i]=son1[i]=0;TP[i]=-INF;
P[i].clear();
}
for(int i=1;i<=N;i++)scanf("%d",&A[i]);
for(int i=1,x;i<=N;i++)scanf("%d",&x),A[i]-=x;
if(N==1){
printf("%d\n",A[1]);
continue;
}
for(int i=1,x,y;i<N;i++){
scanf("%d%d",&x,&y);
P[x].push_back(y);
P[y].push_back(x);
}Ans=-INF;P[1].push_back(0);
DFS(1,0);
if(P[1].size()!=2)TP[1]=INF;
else TP[1]=A[1];
DFS2(1,0);
Ans=F0[1][0];
for(int i=2;i<=N;i++){
if(P[i].size()==1)Ans=max(Ans,TP[i]);
else Ans=max(Ans,min(F0[i][0],TP[i]));
}
printf("%lld\n",Ans);
}
}