本文共 3795 字，大约阅读时间需要 12 分钟。

Acesrc and Travel

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 1394    Accepted Submission(s): 368  

Problem Description

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  spots in Hong Kong, and  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 th spot, Zhang will obtain satisfactory value , and Liu will obtain . 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  , denoting the number of test cases.

For each test case, the first line contains a single integer  , denoting the number of spots. Each of the next two lines contains  integers, and  , denoting the  satisfactory value of Zhang and Liu for every spot, respectively. Each of the last  lines contains two integers  , denoting a bus route between the th spot and the th spot. It is reachable from any spot to any other spot through these bus routes. It is guaranteed that the sum of  does not exceed .

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

换根dp我只会dp求和类似的换根，可这里是维护最大值最小值换根，顿时就慌了。不慌，来看许老师的题解。自从看了许老师的题解，我顿时感觉自己学到了很多。

下图来自：

所以面对最大值最小值的dp转移方程，我们要做的就是对于一个节点u，换根到v的时候，dp[u]重新转移一下，在不包含v的情况下。（学英语口语学多了，说话方式有点英语语法化了），那么如何处理？就是定义一个前缀最大最小值即可。

代码：

#include
   
    using namespace std;typedef long long ll;const int N=1e5+10;const ll inf=1e16;int a[N],b[N],n,u,v;vector
    
     G[N];vector
     
      
        >mx[N];ll dp[2][N],ans;void dfs(int u,int fa){    dp[0][u]=inf;    dp[1][u]=-inf;    for(int v:G[u])    {        if(v==fa) continue;        dfs(v,u);        dp[0][u]=min(dp[0][u],dp[1][v]);        dp[1][u]=max(dp[1][u],dp[0][v]);    }    if(dp[0][u]==inf) dp[0][u]=dp[1][u]=0;//叶子节点    dp[0][u]+=a[u]-b[u];    dp[1][u]+=a[u]-b[u];}void dfs1(int u,int fa){    dp[0][u]=inf;    dp[1][u]=-inf;    for(int v:G[u])//预处理前缀最大值，后缀最大值    {        dp[0][u]=min(dp[0][u],dp[1][v]);        dp[1][u]=max(dp[1][u],dp[0][v]);        mx[u].push_back(make_pair(dp[0][u],dp[1][u]));    }    //if(dp[0][u]==inf) dp[0][u]=dp[1][u]=0;    dp[0][u]+=a[u]-b[u];    dp[1][u]+=a[u]-b[u];    ans=max(ans,dp[0][u]);    ll t1=inf,t2=-inf;    for(int i=G[u].size()-1;i>=0;--i)    {        int v=G[u][i];        dp[0][u]=t1;        dp[1][u]=t2;        if(i)        {            dp[0][u]=min(dp[0][u],mx[u][i-1].first);            dp[1][u]=max(dp[1][u],mx[u][i-1].second);        }        if(dp[0][u]==inf) dp[0][u]=dp[1][u]=0;//注意可能是叶子节点的情况        dp[0][u]+=a[u]-b[u];        dp[1][u]+=a[u]-b[u];        t1=min(t1,dp[1][v]);        t2=max(t2,dp[0][v]);        if(v!=fa) dfs1(v,u);    }}int main(){    int _;cin>>_;while(_--)    {        scanf("%d",&n);        for(int i=1;i<=n;++i) scanf("%d",&a[i]);        for(int i=1;i<=n;++i)        {            scanf("%d",&b[i]);            G[i].clear();            mx[i].clear();        }        for(int i=1;i
      
     
    
   

 

转载地址：https://ccsudeer.blog.csdn.net/article/details/100087035 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！