2019杭电多校 hdu6662 Acesrc and Travel （树形dp

http://acm.hdu.edu.cn/showproblem.php?pid=6662

题意：有两个人在树上博弈，每个点节点有两个分数a[i]和b[i]，先手先选择一个点，后手在先手选的点的相邻点中选择一个点，然后先手在后手选的点的相邻点中选择一个两个人都没有走过的点，直到不能走，游戏就结束。一个人走到节点x，那么先手会获得分数a[x]，后手就会会获得分数b[x]。最后询问先手能获得与后手的差值最大值。

思路：先手固定好位置后，后手走。有两种走法，向下和向上。

向下好办，用down[i][0]表示我从i走到i的儿子后所能得到的最大值，down[i][1]为对手走的最小值,那么down[i][0] = v[i]+max(down[son][1]), down[i][1]=v[i]+min(down[son][0])

向上的话，走完后对面也分为向上或向下。

向下走时，不能走当前上去的路，所以存每个点向下走的最值和次值，当最值和上去那条路得出的值相同，就换成次值。

向上走时，从上到下一路维护即可。

 #include<bits/stdc++.h>

 #define ll long long

 #define rep(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 const int maxn = 1e5+;

 const ll inf = 0x3f3f3f3f3f3f3f3f;

 ll a[maxn],b[maxn];

 int head[maxn],fa[maxn],to[maxn<<],nex[maxn<<],now;

 void add(int a,int b){

     nex[++now] = head[a];

     head[a] = now;

     to[now] = b;

 }

 ll down[maxn][][],up[maxn][];

 bool lef[maxn];

 void dfs(int p){

     down[p][][] = down[p][][] = -inf;

     down[p][][] = down[p][][] = inf;

     lef[p] = ;

     for(int i=head[p];i;i=nex[i]){

         if(to[i]==fa[p]) continue;

         lef[p] = ;

         fa[to[i]] = p;

         dfs(to[i]);

         if(down[to[i]][][]+a[p]>=down[p][][]){

             down[p][][] = down[p][][];

             down[p][][] = down[to[i]][][]+a[p];

         }

         else if(down[to[i]][][]+a[p]>=down[p][][]){

             down[p][][] = down[to[i]][][]+a[p];

         }

         if(down[to[i]][][]+a[p]<=down[p][][]){

             down[p][][] = down[p][][];

             down[p][][] = down[to[i]][][]+a[p];

         }

         else if(down[to[i]][][]+a[p]<=down[p][][]){

             down[p][][] = down[to[i]][][]+a[p];

         }

     }

     if(lef[p]) down[p][][] = down[p][][] = a[p];

 }

 ll Abs(ll a){

     return a>?a:-a;

 }

 void Dfs(int p){

     if(fa[p]==-) up[p][] = up[p][] = inf;

     else {

         up[p][] = inf;

         ll _down = down[fa[p]][][];

         if(_down==a[fa[p]]+down[p][][])

             _down = down[fa[p]][][];

         if(Abs(_down)!=inf)

             up[p][] = min(up[p][],a[p]+_down);

         if(fa[p]!=)

             up[p][] = min(up[p][],a[p]+up[fa[p]][]);

         if(up[p][]==inf)

             up[p][] = a[p]+a[fa[p]];

         up[p][] = -inf;

         _down = down[fa[p]][][];

         if(_down==a[fa[p]]+down[p][][])

             _down=down[fa[p]][][];

         if(Abs(_down)!=inf)

             up[p][]=max(up[p][],a[p]+_down);

         if(fa[p]!=)

             up[p][]=max(up[p][],a[p]+up[fa[p]][]);

         if(up[p][]==-inf)

             up[p][]=a[p]+a[fa[p]];

     }

     for(int i=head[p];i;i=nex[i]){

         if(to[i]==fa[p])continue;

         Dfs(to[i]);

     }

 }

 int main(){

     ios::sync_with_stdio();

     cin.tie();

     cout.tie();

     int t;

     cin>>t;

     while(t--){

         memset(head,,sizeof head);

         now = ;

         int n;

         cin>>n;

         rep(i,,n) cin>>a[i];

         rep(i,,n) cin>>b[i], a[i]-=b[i];

         rep(i,,n-){

             int u,v;

             cin>>u>>v;

             add(u,v);

             add(v,u);

         }

         if(n==){

             cout<<a[]<<endl;

             continue;

         }

         fa[] = -;

         dfs();

         Dfs();

         ll ans = -inf;

         for(int i=;i<=n;i++){

             ll res = inf;

             if(!lef[i]) res = min(res,down[i][][]);

             if(i!=) res = min(res,up[i][]);

             ans = max(ans,res);

         }

         cout<<ans<<endl;

     }

     return ;

 }