树捕获问题在哪里放置另一个玩家以获得最高分

Question

给定一个二叉树。两个玩家正在玩一个游戏，每次两个玩家同时捕获所有相邻节点。当没有玩家可以再占领节点时，游戏结束并计算结果。

如果一个玩家占领了相邻节点，所有这些节点都被认为是该玩家的。

给定player1的节点，player2应该放在哪里，这样player2得到的节点数量最多。

如果有共同邻居的问题，考虑无人捕获。

我在网上搜索过，没有找到类似的问题

在游戏开始时，您可以将其视为森林。

Answer 1

如果我正确理解规则，那么将第二个玩家定位在与第一个玩家节点相邻的节点之一上是有意义的。

因为图是一棵树，所以每个内部节点都是一个关节点：通过捕获这样的节点，图实际上分裂成不连通的图。因此，在有两名玩家的情况下，一名玩家只能到达另一名玩家生成的断开连接图中的一个节点。

让我们假设玩家一在一个有两个 children 和一个 parent 的内部节点上。该玩家因此将图分为三个不连接的图：左子树，右子树，最后是可以从 parent 节点到达但不能通过玩家节点到达的所有节点。

另一个玩家只能放在这三个图中的一个中。第一个玩家可以免费访问其他两个。第二个玩家不可能在那里产生影响。所以这意味着最好将第二个玩家放在三个断开连接的图中最大的一个中。那个断开的图中节点的选择很简单：选择第一个玩家可以直接访问的节点，这样他们甚至不能"enter"那个断开的图形。第二个玩家因此 "owns" 那棵树，并且可以完全捕获它。

因此，可能的算法需要获取与玩家节点相邻的三个断开连接的图的大小。首先定义使用简单的递归算法来获取（子）树的大小：

function getSizeTree(root):
    if root == NIL:
        return 0
    else:
        return 1 + getSizeTree(root.left) + getSizeTree(root.right)

然后对于给定的 root 树，以及放置第一个 player1 的节点，我们可以确定 player2 的最佳选择，如下所示：

function getBestForPlayer2(root, player1):
    sizeAll = getTreeSize(root)
    sizeLeft = getTreeSize(player1.left)
    sizeRight = getTreeSize(player1.right)
    sizeParent = sizeAll - sizeLeft - sizeRight - 1

    maxSize = max(sizeLeft, sizeRight, sizeParent)
    if sizeLeft == maxSize:
        player2 = root.left
    else if sizeParent == maxSize:
        player2 = root.parent
    else:
        player2 = root.right
    return player2

树捕获问题在哪里放置另一个玩家以获得最高分

Tree Capturing problem where to place another player for maximum score

algorithm

binary-tree

data-structures