D 和 V 的博弈游戏 [思维题]

$D和V的博弈游戏$D和V的博弈游戏

$Description$Description

$Solution$Solution

前言: 这道题目状态的转移及代码的实现都较为简单, 但是证明过程却并不是那么轻松… 也许是我太蒻了吧

这里先给出实现核心,具体可以先看后面详解.

$设max\_v\left[i\right],min\_v\left[i\right]表示i为根的子树,David,Van所能取得的各自的最优值.$设max_v[i],min_v[i] 表示 i 为根的子树,David,Van所能取得的各自的最优值.
$注:max\_v\left[i\right]表示在i子树中David能取到第max\_v\left[i\right]大的数,表排名.$注:max_v[i]表示在 i 子树中David能取到第max_v[i]大的数,表排名.

对给出的树执行 $DFS$DFS, 设当前节点为 $i$i, $to\in son\left[i\right]$ to∈son[i],
叶子节点 初值 $max\_v\left[i\right]=min\_v\left[i\right]=1,$max_v[i]=min_v[i]=1,

1. $i为David点$i 为David点,
   $max\_v\left[i\right]=max\left(max\_v\right[to\left]\right)$max_v[i] =max(max_v[to])
   $min\_v\left[i\right]={\sum }_{to\in son\left[i\right]}min\_v\left[to\right]$min_v[i]=∑to∈son[i]​min_v[to]
   
2. $i为Van点$i 为Van点,
   $max\_v\left[i\right]={\sum }_{to\in son\left[i\right]}max\_v\left[to\right]$max_v[i] =∑to∈son[i]​max_v[to]
   $min\_v\left[i\right]=min\left(min\_v\right[to\left]\right)$min_v[i] = min(min_v[to])
   

$接下来是详细的解答过程:$接下来是详细的解答过程:

$如图1-1$如图1−1, 重点说明当前节点为 $Van$Van时如何操作,

$I.情况:$I.情况: $子树仅包括叶子节点$子树仅包括叶子节点
首先要明确: $从树上任意节点出发向下,最后必定到达子节点全部是叶子的节点.$从树上任意节点出发向下,最后必定到达 子节点全部是叶子 的节点.
也就是图中画 $红框$红框 的子树.
这个情况保证了 递归边界 的存在.
此时直接 $max\_v\left[i\right]=min\_v\left[i\right]=1$max_v[i]=min_v[i]=1 即可, 对应上方的 初始化

$II.情况:$II.情况: $子树包括一个叶子节点和一个D节点$子树包括一个叶子节点和一个D节点
设该叶子节点的值为 $t$t, 最后取得 $res$res, 考虑 $Van$Van 如何走,

1. 若 $t=max$t=max, 则 $Van$Van 必定会走 $D$D 节点, $res=ma{x}_{次}$res=max次​.
2. 若 $t=ma{x}_{次}$t=max次​, 此时 $D$D 节点子树可以取得 $max$max 值, 则 $Van$Van 会往 $t$t 走, $res=ma{x}_{次}$res=max次​
3. 若 $t=mid$t=mid, 此时 $res=mid$res=mid.

根据列举的三种情况, 发现 若不将 $t$t 的值置为 $max$max, 则答案不会更优.
扩展到多个 叶子节点, 同理可得 红色字体成立.

$III.情况:$III.情况: $子树包括两个D节点$子树包括两个D节点
若 $Van$Van 走了红节点, 必定是因为 走绿节点会使得 $res$res 更大,
又因为绿节点中取得最大值 $max\_t$max_t 时, 需要 $max\_t-1$max_t−1 个结点将其 $\mathrm{\"}垫上去\mathrm{\"}$"垫上去".
这也就说明了绿节点中所有的数值 比 红节点中 最大数值 要大,
进而说明 红节点 取得的最大数值在这颗子树中的排名为 $max\_v\left[绿\right]+max\_v\left[红\right]$max_v[绿]+max_v[红].

推广到含多个 $D$D 节点的情况, 可以得出结论: $max\_v\left[i\right]={\sum }_{to\in son\left[i\right]}max\_v\left[to\right]$max_v[i] =∑to∈son[i]​max_v[to] ,
也就是上方的式子.

如果仔细观察, 可以发现 $情况II.$情况II. 与 $情况III.$情况III. 是可以看做同一类的,
因此简化转移的式子.

$David$David 节点的处理方式与 $Van$Van 的具有对称性, 这里不再赘述.

$END$END.

$Code$Code