牛客挑战赛 B - 树上博弈 -- 题解

目录

??B - 树上博弈

题目描述

输入描述:

输出描述:

输入

输出

思路：

代码：

---

?

??B - 树上博弈

B-树上博弈_牛客挑战赛71 (nowcoder.com)

?

题目描述

有一棵共有 nnn 个结点的有根树，规定 1?号节点为根节点。

除根结点外，每个结点都有一些金币。具体地，编号为 iii 的结点上有 ci个金币（2?i?n）。

游戏开始时，有一只棋子位于根节点，而后 Alice 和 Bob 轮流进行如下操作：
?

• 将棋子从当前结点 x移动到其任意一个子孙结点?y，并且该玩家获得结点 y上所有的金币。

我们说结点 x 为结点 y 的子孙结点，是指 x≠y?并且结点 y?位于从结点 x到根结点的最短路径上。

当棋子位于叶子结点时无法继续进行操作，此时游戏结束。

记游戏结束时 Alice 有 a 个金币，Bob 有 b 个金币。

Alice 的目标是让 a?b?尽可能大，Bob 的目标则与之相反。

Alice 和 Bob 都很聪明，他们都会采取最优策略进行游戏。

现在由 Alice 先手开始游戏，请你预测游戏结束时 a?ba - ba?b 的值。

输入描述:

本题包含多组测试数据。

第一行一个整数 T (1?T?10^5)，表示测试数据的数量。

对于每组测试数据：

第一行有一个整数 n (2?n?2×10^5)，表示树的结点数量。
第二行有 n?1个整数 c2,c3,…,cn(0?ci?10^9)，表示结点 iii 上有 ci个金币。
?第三行有 n?1个整数 p2,p3,…,pn(1?pi<i)，表示结点 iii 的父结点为结点 pi

输入数据保证所有测试数据的 n之和 ∑n?2×10^5

输出描述:

每组测试数据输出一行一个整数，表示游戏结束时 a?b?的值。

示例1

输入

5
5
2 3 4 5
1 2 3 4
5
5 1 1 1
1 2 3 4
5
5 4 3 1
1 2 3 4
5
520 114514 1919810 998244353
1 2 2 2
5
998244353 1919810 114514 520
1 2 2 2

输出

5
4
3
998244353
996324543

思路：

这是一个简单的dp问题，但是需要注意的是，他下一次走的结点是任意的，可以走到任意一个子孙结点去，但是不能往上走，就是每次往下任意走。（我比赛这里看错了，以为一次只能走一步），然后又因为是任意走，所以第一步a一定会选择一个最大的，并且之后b会选择一个在a下方中最大的，对于剩下的结点来说，如果选择能让a-b，变得更小，a一定会直接选择叶结点，让他提前终止，如果剩下的结点，如果选择能让a-b，变得更大，b一定会提前终止这个游戏。然后又因为这是一个博弈问题，他们都会走对于自己最优的位置，?所以分别求最大。

 // dp[i][j] if j == 0, 表示当前处于第i个结点，并且一定不选择第i个结点能获得的最大钱数。
// dp[i][j] if j == 1, 表示当前处于第i个结点，并且可以选择第i个结点能获得的最大钱数。
public static void dfs(int x) {
        for (int i = 0; i < g.get(x).size(); i++) {
            int y = g.get(x).get(i);
            dfs(y);
               // 这里都可能选择到dp[y1][1] 使得dp[x][0] 和dp[x][1]都变为最大，
            // 怎么排除，这种不合法的选择方案。
            // Math.max(arr[x] - dp[x][0], dp[x][1]); 通过max 让他选择x这个结点
            // 如果还是 dp[y1][1] 是更优选择，但是递归时不依靠dp[y][0]，
            // 所以相当于在出现冲突时，强行让dp[x][1]的优先级更高
            dp[x][1] = Math.max(dp[x][1], dp[y][1]); 
            dp[x][0] = Math.max(dp[x][0], dp[y][1]);
        }
        dp[x][1] = Math.max(arr[x] - dp[x][0], dp[x][1]);
    }

代码：

import java.io.*;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * @ProjectName: study3
 * @FileName: Ex36
 * @author:HWJ
 * @Data: 2023/12/8 19:35
 */
public class Main {
    static Vector<Vector<Integer>> g;
    static long[] arr;
    static long[] maxx;
    static long[][] dp;
    public static void main(String[] args) {
        int t = input.nextInt();
        for (int o = 0; o < t; o++) {
            int n = input.nextInt();
            arr = new long[n + 1];
            dp = new long[n + 1][2];
            g = new Vector<>();
            for (int i = 0; i < n + 1; i++) {
                g.add(new Vector<>());
            }
            for (int i = 1; i < n; i++) {
                arr[i + 1] = input.nextInt();
            }
            for (int i = 1; i < n; i++) {
                int a = input.nextInt();
                g.get(a).add(i + 1);
            }
            dfs(1);
            out.println(dp[1][1]);
        }
        out.flush();
        out.close();
    }
    

    public static void dfs(int x) {
        for (int i = 0; i < g.get(x).size(); i++) {
            int y = g.get(x).get(i);
            dfs(y);
            dp[x][1] = Math.max(dp[x][1], dp[y][1]);
            dp[x][0] = Math.max(dp[x][0], dp[y][1]);
        }
        dp[x][1] = Math.max(arr[x] - dp[x][0], dp[x][1]);
    }


    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Input input = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}