2019HDU多校-Day8

Posted on | Edited on | Views:

F. Acesrc and Travel

题意

给一颗树，每个点有两个权值 $a_i,b_i$ ，两个人博弈，交替选择节点，A 获得 $a_i$ ，B 获得 $b_i$ ，每次只能选取与上一个人相邻的节点。

题解

先以任意点为根节点，算出这种情况的结果，再利用换根的方法求出所有节，要注意处理好根节点和叶节点的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
vii node[N];
ll w[N];
pll dp[N][2];
ll ans;
void dfs(int u,int fa){
    ll max_fi=-inf,max_se=-inf,min_fi=inf,min_se=inf;
    if(fa&&node[u].size()==1){//非根叶节点
        dp[u][0]=pll(w[u],-inf);
        dp[u][1]=pll(w[u],inf);
        return;
    }
    for(auto i:node[u]){
        if(i!=fa){
            dfs(i,u);
            if(dp[i][0].fi+w[u]<min_fi){
                min_se=min_fi;
                min_fi=dp[i][0].fi+w[u];
            }else min_se=min(min_se,dp[i][0].fi+w[u]);
            
            if(dp[i][1].fi+w[u]>max_fi){
                max_se=max_fi;
                max_fi=dp[i][1].fi+w[u];
            }else max_se=max(max_se,dp[i][1].fi+w[u]);
        }
    }
    dp[u][0]=pll(max_fi,max_se);
    dp[u][1]=pll(min_fi,min_se);
}
void dfs2(int u ,int fa ,ll max1,ll min0){
    if(u!=1){
        if(node[u].size()==1) ans=max(ans,min0+w[u]);
        else{
            if(min0+w[u]<dp[u][1].fi)ans=max(ans,min0+w[u]);
            else ans=max(ans,dp[u][1].fi);
        }
    }
    for(int v:node[u]){
        if(v!=fa){
            ll tmin,tamx;
            if(dp[u][1].fi==dp[v][0].fi+w[u])tamx=min(min0+w[u],dp[u][1].se);
            else tamx=min(min0+w[u],dp[u][1].fi);

            if(dp[u][0].fi==dp[v][1].fi+w[u])tmin=max(max1+w[u],dp[u][0].se);
            else tmin=max(max1+w[u],dp[u][0].fi);
            // cout<<v<<' '<<tmin<< ' '<<tamx<<endl;
            dfs2(v,u,tamx,tmin);
        }
    }

}
int main() {
    int t,n,u,v,x;
    in(t);
    while(t--){
        in(n);
        for1(i,n)in(w[i]);
        for1(i,n){
            node[i].clear();
            in(x);
            w[i]-=x;
        }
        for0(i,n-1){
            in(u,v);
            node[u].pu_b(v);
            node[v].pu_b(u);
        }
        dfs(1,0);
        ans=dp[1][1].fi;
        if(node[1].size()==1) dfs2(node[1][0],1,w[1],w[1]);// 特判根节点只连有一个点的情况
        else dfs2(1,0,-inf,inf);
        out(ans,1);
    }
    return 0;
}