題干：

Acesrc is a famous tourist at Nanjing University second to none. During this summer holiday, he, along with Zhang and Liu, is going to travel to Hong Kong. There are?nnspots in Hong Kong, and?n?1n?1?bidirectional sightseeing bus routes connecting these spots. They decide to visit some spots by bus.?

However, Zhang and Liu have different preferences for these spots. They respectively set a satisfactory value for each spot. If they visit the?iith spot, Zhang will obtain satisfactory value?aiai, and Liu will obtain?bibi. Starting with Zhang, they alternately decide the next spot to visit for the sake of fairness. There must be a bus route between the current spot and the next spot to visit. Moreover, they would never like to visit a spot twice. If anyone can't find such a next spot to visit, they have no choice but to end this travel.?

Zhang and Liu are both super smart competitive programmers. Either want to maximize the difference between his total satisfactory value and the other's. Now Acesrc wonders, if they both choose optimally, what is the difference between total satisfactory values of Zhang and Liu?

Input

The first line of input consists of a single integer?TT?(1≤T≤30)(1≤T≤30), denoting the number of test cases.?

For each test case, the first line contains a single integer?nn?(1≤n≤105)(1≤n≤105), denoting the number of spots. Each of the next two lines contains?nn?integers,?a1,a2,?,ana1,a2,?,an?and?b1,b2,?,bnb1,b2,?,bn?(0≤ai,bi≤109)(0≤ai,bi≤109), denoting the?
satisfactory value of Zhang and Liu for every spot, respectively. Each of the last?n?1n?1?lines contains two integers?x,yx,y?(1≤x,y≤n,x≠y)(1≤x,y≤n,x≠y), denoting a bus route between the?xxth spot and the?yyth spot. It is reachable from any spot to any other spot through these bus routes.?

It is guaranteed that the sum of?nn?does not exceed?5.01×1055.01×105.

Output

For each test case, print a single integer in one line, the difference of total satisfactory values if they both choose optimally.

Sample Input

1 3 1 1 1 0 2 3 1 2 1 3

Sample Output

-1

題目大意：

n個點的一棵無根無向樹，每個點代表一個景點，有A和B兩個人，A先手。每個人輪流選擇下一個景點去哪里（選擇的景點必須和當(dāng)前景點有連邊），走到第i個景點的時候，A會獲得ai點滿意度，B會獲得bi點滿意度，每個景點只能走一次，當(dāng)走到無法再走的時候，游戲結(jié)束。現(xiàn)在已知A和B都以最佳策略選取景點，最佳策略指的是自己的總滿意度和對方的總滿意度的差值最大。求這個最大差值。

解題報告：

首先簡化一下題意，可以構(gòu)造c[i]=a[i]-b[i]，那么兩人的總滿意度的差值記為，所以也就是A想讓sum最大，B想讓sum最小。然后考慮樹形dp。

第一遍dfs處理出以每個點u為起點，只能往孩子節(jié)點v[i]走的最大值和最小值。

第二遍dfs處理出每個點u為起點，往父親節(jié)點走的最大值和最小值。這一點可以用set做到。

對于第二遍dfs具體實現(xiàn)的時候就是對于每一個e=(u,v)，先處理出一個數(shù)組g[v][2]代表以他為起點，向原父節(jié)點走，最大值和最小值，然后再去dfs(v,cur)這樣。

比賽的時候兩個細節(jié)沒寫好、、、主要還是dp狀態(tài)寫的時候和轉(zhuǎn)移的時候有點亂了，導(dǎo)致有一點邏輯錯誤

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e5+5; const ll INF = 1e18; ll dp[MAX][2];//dp[i][0] Zhang dp[i][1] Liu //dp[i][0] max{a[i]-b[i]} dp[i][1] min{a[i]-b[i]} ll g[MAX][2]; ll a[MAX],b[MAX]; multiset<ll> s0[MAX],s1[MAX]; struct Edge {int v,ne; } e[MAX<<1]; int head[MAX],tot; int n; void add(int u,int v) {e[++tot].v = v;e[tot].ne = head[u]; head[u] = tot; } void dfs(int cur,int fa) {int yz = 1;for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(v == fa) continue;yz=0;dfs(v,cur);}if(yz == 1) { // s0[cur].insert(a[cur]-b[cur]);s1[cur].insert(a[cur]-b[cur]);dp[cur][1]=dp[cur][0] = a[cur]-b[cur];return;}for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(v == fa) continue;dp[cur][0] = max(dp[cur][0],dp[v][1]+a[cur]-b[cur]);//Zhang 決策 = dp[cur][1] = min(dp[cur][1],dp[v][0]+a[cur]-b[cur]);s0[cur].insert(dp[v][1]+a[cur]-b[cur]);s1[cur].insert(dp[v][0]+a[cur]-b[cur]);} } void dfs2(int cur,int fa) {ll qq0,qq1;if(fa!=0) s0[cur].insert(g[cur][0]),s1[cur].insert(g[cur][1]);for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(v == fa) continue;auto it0 = s0[cur].find(dp[v][1]+a[cur]-b[cur]);ll tmp0 = *it0;s0[cur].erase(it0);auto it1 = s1[cur].find(dp[v][0]+a[cur]-b[cur]);ll tmp1 = *it1;s1[cur].erase(it1);if(s0[cur].empty()) g[v][0]=g[v][1]=a[cur]-b[cur]+a[v]-b[v];//s0[v].insert(a[v] - b[v]),s1[v].insert(a[v]-b[v]);else {qq0 = (*s0[cur].rbegin()),qq1 = (*s1[cur].begin()); // if(fa != 0) { // g[v][0] = min(g[cur][1]+a[v]-b[v],(qq1) + a[v] - b[v]); // g[v][1] = max(g[cur][0]+a[v]-b[v],(qq0) + a[v] - b[v]); // } // else {g[v][0] = qq1 + a[v] - b[v];g[v][1] = qq0 + a[v] - b[v]; // }}s0[cur].insert(tmp0);s1[cur].insert(tmp1);dfs2(v,cur);}} int main() {int t;cin>>t;while(t--) {scanf("%d",&n);tot=0;for(int i = 1; i<=n; i++) head[i] = -1,s0[i].clear(),s1[i].clear();for(int i = 1; i<=n; i++) scanf("%lld",a+i),dp[i][0]=-INF,dp[i][1]=INF;for(int i = 1; i<=n; i++) scanf("%lld",b+i);for(int u,v,i = 1; i<n; i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);dfs(1,0);//g[1][0]=g[1][1]=a[1]-b[1];dfs2(1,0);ll ans = -INF;for(int i = 1; i<=n; i++) { // printf("***%d %lld\n",i,*s1[i].begin());ans = max(*s1[i].begin(),ans);}printf("%lld\n",ans);} return 0 ; } /* 1000 錯誤樣例 8 1 4 2 0 4 1 0 3 4 0 0 1 0 4 4 4 6 5 5 1 6 4 2 4 7 5 3 5 3 8 錯誤樣例 7 2 3 4 5 5 5 5 2 2 1 13 8 3 3 1 2 1 3 3 4 3 5 5 6 5 7 錯誤樣例 6 1 3 3 4 2 4 5 7 2 1 1 3 1 2 1 3 1 4 1 5 1 6 */

?

總結(jié)

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

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