Acesrc and Travel(换根树DP)

题目链接

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

题目大意

n个点由n-1条边链接,保证任意两点间有一条通路,每个点有一个自己的权值a[i]和b[i],Alice和Bob轮流选择下一步要去的点,Alice想要让路径的总a[i]-b[i]的差尽可能大,Bob相反,两人均足够聪明。问最终最大的差是多少。

解题思路

如果固定了起点,那么就是一个简单的树形DP,但是现在起点不固定,所以我们需要O(1)的转移起点,首先用树形DP处理出1号节点为根的时候每个点作为先手点的最大值次大值和每个点作为后手节点的最大值次大值。
转移时对于新的根节点有两种可能,向上(父亲节点)走更优,和向下走更优,向下走的情况在以1为根的时候已经处理过了,向上走的时候需要判断一下,如果要走父亲节点及它的子树的话,如果当前节点是父节点最大值要走的那个节点,那么以这个节点为根向上走的话肯定要去走父亲节点子节点中次大值的节点,否则一定要去走父亲节点子节点中最大值的那个节点。如果不走父亲节点的子树而是继续向上走的话就直接用以父亲为根的最优值转移即可。

代码

#include <bits/stdc++.h>
const int maxn=1e5+100;
using namespace std;
#define ll long long
int a[maxn],b[maxn],c[maxn],du[maxn];
long long dp[maxn][2][2];//first[0-xian 1-hou] second[0-max  1-second max]
long long p[maxn],q[maxn];
vector<int> edge[maxn];
int n;
void init() {
    for(int i=0; i<=n; i++) {
        du[i]=0;
        dp[i][0][0]=dp[i][0][1]=-999999999999999;
        dp[i][1][0]=dp[i][1][1]=999999999999999;
        edge[i].clear();
    }
}
void dfs1(int u,int fa) {
    for(int v:edge[u]) {
        if(v==fa)
            continue;
        du[u]++;
        dfs1(v,u);
        if(dp[u][0][0]<dp[v][1][0]+c[u])
            dp[u][0][1]=dp[v][1][0]+c[u],swap(dp[u][0][0],dp[u][0][1]);
        else if(dp[u][0][1]<dp[v][1][0]+c[u])
            dp[u][0][1]=dp[v][1][0]+c[u];
        if(dp[u][1][0]>dp[v][0][0]+c[u])
            dp[u][1][1]=dp[v][0][0]+c[u],swap(dp[u][1][0],dp[u][1][1]);
        else if(dp[u][1][1]>dp[v][0][0]+c[u])
            dp[u][1][1]=dp[v][0][0]+c[u];
    }
    if(!du[u]) {
        dp[u][0][0]=dp[u][0][1]=dp[u][1][0]=dp[u][1][1]=c[u];
    }
}
void dfs2(int u,int fa) {
    for(int v:edge[u]) {
        if(v==fa)
            continue;
        long long r;
        if(du[u]==1) {
            p[v]=q[u]+c[v];
            q[v]=p[u]+c[v];
        } else {
            if(dp[u][0][0]==dp[v][1][0]+c[u])
                r=dp[u][0][1];
            else
                r=dp[u][0][0];
            if(u!=1)
                r=max(r,q[u]);
            p[v]=r+c[v];
            if(dp[u][1][0]==dp[v][0][0]+c[u])
                r=dp[u][1][1];
            else
                r=dp[u][1][0];
            if(u!=1)
                r=min(r,p[u]);
            q[v]=r+c[v];
        }
        dfs2(v,u);
    }
}
int main() {
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--) {
        cin>>n;
        init();
        for(int i=1; i<=n; i++) {
            cin>>a[i];
        }
        for(int i=1; i<=n; i++) {
            cin>>b[i];
            c[i]=a[i]-b[i];
        }
        int u,v;
        for(int i=1; i<n; i++) {
            cin>>u>>v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        dfs1(1,0);
        p[1]=q[1]=c[1];
        dfs2(1,0);
        long long ans=-999999999999999;
        p[1]=dp[1][1][0];
        for(int i=1; i<=n; i++) {
            if(du[i])
                ans=max(ans,min(dp[i][1][0],p[i]));
            else
                ans=max(ans,p[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注