HDU多校第八场 1006 Acesrc and Travel —— 树形DP + 换根

题目链接：点我啊╭(╯^╰)╮

题目大意：

    一棵无根树，每个点有两个点权 $a_i$ 和 $b_i$
    $Zhang$ $and$ $Liu$ 轮流选，$Zhang$ 选一个点可以得到 $a_i$
    $Liu$ 选一个点可以得到 $b_i$，选过的点不能再选
    两人都想让自己得到的权值更多且和另一个人的差值更大
    $Zhang$ 先选，问最后的结果的是多少

解题思路：

    假设有根，$a[i]=a[i]?b[i]$
    $dp[u][0]$ 表示 $Zhang$ 选择了 $u$ 的结果，$dp[u][1]$ 表示 $Liu$ 选择了 $u$ 的结果
    $dp[u][0]=min(dp[v][1]+a[u])$
    $dp[u][1]=max(dp[v][0]+a[u])$
    因为一个人选择了之后，另一个人会反向影响

    然后开始换根
    保留每个结点的前两小值和后两大值
    每次换根时只改变 $rt$ 与 $son$ 两个结点的信息
    更新即可
    换根类似题：HDU多校第三场 1011 Squrirrel —— 换根 + 树形DP

核心：树形DP + 换根

#include<bits/stdc++.h>
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
#define fi first
#define se second
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
const int maxn = 1e5 + 5;
int T, n, a[maxn];
vector <int> g[maxn];
map <pii, int> m0[maxn], m1[maxn];
ll dp[maxn][2], ans;inline void add0(int u, ll val, int v){m0[u][{val, v}]++;if(m0[u].size() > 2) m0[u].erase(--m0[u].end());
}
inline void add1(int u, ll val, int v){m1[u][{val, v}]++;if(m1[u].size() > 2) m1[u].erase(m1[u].begin());
}inline void get(int u){if(!m0[u].size()) {dp[u][0] = dp[u][1] = a[u];return;}dp[u][0] = m0[u].begin()->fi.fi;dp[u][1] = (--m1[u].end())->fi.fi;
}inline void dfs1(int u, int fa){m0[u].clear(), m1[u].clear();for(auto v : g[u]){if(v == fa) continue;dfs1(v, u);add0(u, dp[v][1] + a[u], v);add1(u, dp[v][0] + a[u], v);}get(u);
}inline void move(int rt, int son){m0[rt].erase( {dp[son][1] + a[rt], son} );m1[rt].erase( {dp[son][0] + a[rt], son} );get(rt);add0(son, dp[rt][1] + a[son], rt);add1(son, dp[rt][0] + a[son], rt);get(son);
}inline void dfs2(int u, int fa){ans = max(ans, dp[u][0]);for(auto v : g[u]){if(v == fa) continue;move(u, v);dfs2(v, u);move(v, u);}
}int main() {scanf("%d", &T);while(T--){ans = -4e18;scanf("%d", &n);for(int i=1; i<=n; i++) scanf("%d", a+i), g[i].clear();for(int i=1, x; i<=n; i++) scanf("%d", &x), a[i] -= x;for(int i=1, u, v; i<n; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs1(1, 0);dfs2(1, 0);printf("%lld\n", ans);}
}