【HDU】【树形DP】6662 Acesrc and Travel_综合

HDU 6662 Acesrc and Travel

题目大意

◇题目传送门◆

两个人在一棵树上博弈， $A$ 走到点 $i$ 会获得 $A_i$ 的收益， $B$ 走到节点 $i$ 会获得 $B_i$ 的收益。 $A$ 可以任意选择一个起始点，然后 $B$ 在 $A$ 选择的点的相邻点且没有被选过的点中选择一个走下去，然后 $A$ 进行相同的操作，现在两人都想最大化与对手的差异，求 $∑Ai?∑Bi\sum A_i-\sum B_i$ 的最大值。

分析

为了方便计算，我们记 $v_i=A_i-B_i$ 。

由于两人均想最大化与对手之间的差异，我们不难发现 $A$ 选择了一个点后， $B$ 一定会选择相邻点中 $v_i$ 最小的；反过来， $A$ 一定会选择最大的 $v_i$ 走下去。

那么考虑这样设计状态：设状态 $f_1(u)$ 为当前两人在节点 $u$ ，接下来该 $A$ 选点，走到以 $u$ 为根的子树中的某个叶子节点的最优的答案；同理，状态 $f_2(u)$ 为该 $B$ 选点时的最优答案。

不难列出状态转移：
$f1(u)=max?v∈son(u){f2(v)+wu}f2(u)=min?v∈son(u){f1(v)+wu}f_1(u)=\max_{v\in son(u)}\{f_2(v)+w_u\}\\f_2(u)=\min_{v\in son(u)}\{f_1(v)+w_u\}$

这样我们就做出了固定一个起点的转移方案。

但这题的起点是不固定的，那么我们考虑换根。

我们再定义 $g_1(u),g_2(u)$ 分别为现在在节点 $u$ ，轮到 $A / B$ 选点且从 $u$ 往父亲走的方案。

那么就有两种转移方式：（其中 $v$ 是 $u$ 的儿子）

往父亲的父亲方向： $g_1(v)=g_2(u)+w_v,g_2(v)=g_2(u)+w_v$ ；
往兄弟方向： $g_1(v)=f_1(u)+w_v,g_2(v)=f_2(u)+w_v$ 。
最后在两种转移方式中取较大值/较小值即可。

注意到我们 $g$ 的转移方向可能和 $f$ 的最优值转移方向相同，所以我们必须记录一下次优值，当发现转移方向是 $f$ 的最优值方向时就用次优值转移。

最后答案为 $max_{i=1}^{N}\{\min(g_1(i),f_2(i))\}$

注意当 $i$ 是叶子节点时，它对答案的贡献仅为 $g_1(i)$

参考代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 1e5;
const ll INF = 1e18;int N, val[Maxn + 5];
vector<int> G[Maxn + 5];
void addedge(int u, int v) {
    G[u].push_back(v);G[v].push_back(u);
}int cnt_son[Maxn + 5];
ll f1[2][Maxn + 5], f2[2][Maxn + 5], g1[Maxn + 5], g2[Maxn + 5];
void PreDFS(int u, int fa) {
    for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];if(v == fa) continue;PreDFS(v, u);cnt_son[u]++;if(f1[0][u] < f2[0][v] + val[u])f1[1][u] = f1[0][u], f1[0][u] = f2[0][v] + val[u];else if(f1[1][u] < f2[0][v] + val[u])f1[1][u] = f2[0][v] + val[u];if(f2[0][u] > f1[0][v] + val[u])f2[1][u] = f2[0][u], f2[0][u] = f1[0][v] + val[u];else if(f2[1][u] > f1[0][v] + val[u])f2[1][u] = f1[0][v] + val[u];}if(cnt_son[u] == 0) {
    f1[0][u] = f1[1][u] = val[u];f2[0][u] = f2[1][u] = val[u];}
}
void DFS(int u, int fa) {
    for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];if(v == fa) continue;if(cnt_son[u] == 1) {
    g1[v] = g2[u] + val[v], g2[v] = g1[u] + val[v];} else {
    ll mx = f1[0][u];if(f1[0][u] == f2[0][v] + val[u])mx = f1[1][u];if(u != 1) mx = max(mx, g2[u]);g1[v] = mx + val[v];ll mn = f2[0][u];if(f2[0][u] == f2[0][v] + val[u])mn = f2[1][u];if(u != 1) mn = min(mn, g1[u]);g2[v] = mn + val[v];}DFS(v, u);}
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint _;scanf("%d", &_);while(_--) {
    scanf("%d", &N);for(int i = 1; i <= N; i++) {
    G[i].clear();cnt_son[i] = 0;f1[0][i] = f1[1][i] = -INF;f2[0][i] = f2[1][i] = INF;}for(int i = 1; i <= N; i++)scanf("%d", &val[i]);for(int i = 1; i <= N; i++) {
    int x;scanf("%d", &x);val[i] -= x;}for(int i = 1; i < N; i++) {
    int u, v;scanf("%d %d", &u, &v);addedge(u, v);}PreDFS(1, 0);g1[1] = g2[1] = val[1];DFS(1, 0);ll ans = f2[0][1];for(int i = 2; i <= N; i++) {
    if(G[i].size() == 1) ans = max(ans, g1[i]);else ans = max(ans, min(g1[i], f2[0][i]));}printf("%lld\n", ans);}return 0;
}/**/