题目链接
传送门 http://acm.hdu.edu.cn/showproblem.php?pid=6662
题意
两个绝顶聪明的人在树上玩博弈, 规则是轮流选择下一个要到达的点, 每达到一个点时, 先手和后手分别获得 \(a_i,b_i\)(到达这个点时两个人都会获得) 的权值, 已经经过的点无法再次经过, 直到无法移动则结束游戏, 两人都想最大化自己的权值和减对手权值和, 问先手减后手权值和最大是多少.
思路
换根 \(DP\), 和求树的直径有点类似.
\(dp[i][j]\) 表示在 \(i\) 这个结点状态为 \(j\) 时先手权值和减后手权值和最优是多少,\(j\) 为偶数表示当前是先手, 为奇数时为后手.
转移方程: 我们该 \(dp\) 是倒着推的, 也就是说从游戏结束开始往游戏开始推, 假设当前是先手选择, 那么下一步就是后手移动, 按照题目要求后手一定是想最小化先手减后手权值和, 因此当前一定是从最小的先手减后手权值和转移过来; 如果当前是后手那么就从先手减后手权值和最大转移过来.
需要特别注意的两点是:
从子结点转移过来很好想, 就是子结点中相反状态转移过来, 也就是当前为先手那么从最小过来; 从父亲结点转移过来的时候, 因为一个结点只有一个父亲结点, 因此如果当前是先手, 那么父亲结点也就确定了, 因此它要从父亲结点从其他结点转移过来的最大值转移到当前结点, 后手同理, 枚举起点时由于你枚举之后起点也固定了, 因此对于同一个起点要选择值最小的方向 (因为这里我卡了好久, 好菜啊).
最后枚举答案的时候如果当前点是叶子结点, 那么它的答案是从父亲结点贡献的, 不能由它自己贡献, 因为如果先手选择这个点为起点, 那么后手一定是往父亲结点选.
代码
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- typedef pair<LL, LL> pLL;
- typedef pair<LL, int> pLi;
- typedef pair<int, LL> pil;;
- typedef pair<int, int> pii;
- typedef unsigned long long uLL;
- #define lson (rt<<1),L,mid
- #define rson (rt<<1|1),mid + 1,R
- #define lowbit(x) x&(-x)
- #define name2str(name) (#name)
- #define bug printf("*********\n")
- #define debug(x) cout<<#x"=["<<x<<"]" <<endl
- #define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
- #define IO iOS::sync_with_stdio(false),cin.tie(0)
- const double eps = 1e-8;
- const int mod = 1000000007;
- const int maxn = 100000 + 7;
- const double pi = acos(-1);
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3fLL;
- int t, n, tot, x, u, v;
- int a[maxn], head[maxn], du[maxn];
- LL dp[maxn][6];
- struct edge{
- int v, next;
- }ed[maxn*2];
- void add(int u, int v) {
- ed[tot].v = v;
- ed[tot].next = head[u];
- head[u] = tot++;
- }
- void dfs1(int u, int p) {
- for(int i = head[u]; ~i; i = ed[i].next) {
- int v = ed[i].v;
- if(v == p) continue;
- dfs1(v, u);
- ++du[u];
- if(dp[v][1] <dp[u][0]) {
- dp[u][2] = dp[u][0];
- dp[u][0] = dp[v][1];
- } else {
- dp[u][2] = min(dp[u][2], dp[v][1]);
- }
- if(dp[v][0]> dp[u][1]) {
- dp[u][3] = dp[u][1];
- dp[u][1] = dp[v][0];
- } else {
- dp[u][3] = max(dp[u][3], dp[v][0]);
- }
- }
- if(dp[u][0] == INF) dp[u][0] = dp[u][1] = dp[u][2] = dp[u][3] = 0;
- dp[u][0] += a[u], dp[u][2] += a[u];
- dp[u][1] += a[u], dp[u][3] += a[u];
- }
- void dfs2(int u, int p) {
- for(int i = head[u]; ~i; i = ed[i].next) {
- int v = ed[i].v;
- if(v == p) continue;
- if(du[u] == 1) {
- dp[v][5] = dp[u][4] + a[v];
- dp[v][4] = dp[u][5] + a[v];
- } else {
- if(dp[u][0] == dp[v][1] + a[u]) {
- if(u != 1) dp[v][5] = min(dp[u][2], dp[u][4]) + a[v];
- else dp[v][5] = dp[u][2] + a[v];
- } else {
- if(u != 1) dp[v][5] = min(dp[u][0], dp[u][4]) + a[v];
- else dp[v][5] = dp[u][0] + a[v];
- }
- if(dp[u][1] == dp[v][0] + a[u]) {
- if(u != 1) dp[v][4] = max(dp[u][3], dp[u][5]) + a[v];
- else dp[v][4] = dp[u][3] + a[v];
- } else {
- if(u != 1) dp[v][4] = max(dp[u][1], dp[u][5]) + a[v];
- else dp[v][4] = dp[u][1] + a[v];
- }
- }
- dfs2(v, u);
- }
- }
- int main() {
- #ifndef ONLINE_JUDGE
- FIN;
- #endif
- scanf("%d", &t);
- while(t--) {
- scanf("%d", &n);
- tot = 0;
- for(int i = 1; i <= n; ++i) {
- scanf("%d", &a[i]);
- head[i] = -1;
- du[i] = 0;
- dp[i][0] = dp[i][2] = dp[i][4] = INF;
- dp[i][1] = dp[i][3] = dp[i][5] = -INF;
- }
- for(int i = 1; i <= n; ++i) {
- scanf("%d", &x);
- a[i] -= x;
- }
- for(int i = 1; i < n; ++i) {
- scanf("%d%d", &u, &v);
- add(u, v), add(v, u);
- }
- dfs1(1, 0);
- dp[1][4] = dp[1][5] = a[1];
- dfs2(1, 0);
- LL ans = dp[1][0];
- for(int i = 2; i <= n; ++i) {
- if(du[i] == 0) ans = max(ans, dp[i][4]);
- else ans = max(ans, min(dp[i][4], dp[i][0]));
- }
- printf("%lld\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3160458.html