开新坑啦! TAT
换根DP结合博弈论真的恶心……
Part1. 题面
> 传送门 HDU
有一棵 n 个点的无根树,每个点 u 有两个非负点权 $A_u,B_u$。
Alice 和 Bob 在这棵树上博弈,Alice 先手。第一次操作,先手在树上选任意一个点;然后接下来的操作,每次操作只能选取与上一次 选取的点相邻的、且没有被选过的点。一直选择直到没有可以选择的点为止。
每选择一个点 u(无论是 Alice 还是 Bob 选),Alice 的得分增加 $A_u$,Bob 的得分增加 $B_u$。
两人都希望“自己的得分减对手的得分”尽可能大。假设两人绝顶聪明(awa),输出最终 “Alice 的得分-Bob的得分”。
数据规模:$1\le n\le10^5$;$0\le A_u,B_u\le10^9$。
Part2. 解析
首先分析题目,因为除去第一次可以随意选择,其他操作都必须选择与上一次操作相邻的点,而且不能选择已经选过的点 —— 不难发现最后选出来的是树上的一条链。新定义点 u 的点权为 $(A_u-B_u)$,显然 Alice 要让选出的链上的点权之和增大,Bob 要让它变小。
因为两人都绝顶聪明,那么其实 Alice 走了第一步,之后的所有最优方案都是唯一的。于是决定答案的 其实是第一次选择的点。
所以可以这样理解问题 —— 将第一个选择的点作为树的根节点,然后求出一条从根到叶子节点的链。从这一点可以考虑换根DP。
在树上找链的换根 DP 有两个 dp 数组,f[u][..]
存储的是从 u 开始向子树连接链的答案信息,g[u][..]
存储的是从 u 往祖先跑(可能又折返往另一个子树)连成链的答案信息。两个合起来就能变成一条完整的链,这是这一类型的换根DP的常规套路。
注意到计算 f[u][..]
时,是从下往上递归计算,计算 g[u][..]
时,是从上往下计算。
> Tip
举一个生动形象的栗子:
很多这一类型的题会存储最大值和次大值,这道题也不例外。而且因为这是博弈论,Bob 要最小化链上点权和,而 Alice 要最大化它,所以这道题 f[u][..]
要维护 4 个值:
> Tab
v 是 u 的儿子节点
f[u][0]
:Bob 选 u,Alice 选择 u 的儿子 v,能够取得的最大值(不包含u本身的点权);f[u][1]
:Bob 选 u,Alice 选择 v,能够取得的次大值(不包含u本身);f[u][2]
:Alice 选 u,Bob 选择 v,能够取得的最小值(不包含u);f[u][3]
:Alice 选 u,Bob 选择 v,能够取得的次小值(不包含u);
然后考虑 v 的 dp 值怎么更新 u 的 DP 值:
如果 Alice 选了 u,对应的 dp 数组为
f[u][2/3]
:
那么 v 是由 Bob 选的,于是 Bob 会最小化f[u][2/3]
;
v 之后的一个节点是 Alice 选的,于是 Alice 会最大化从 v 开始的链,也就是取到最大值f[v][0]
,再加上 v 的值val[v]
;
则f[u][2/3]
分别保存了f[v][0]+val[v]
的最小值和次小值。如果 Bob 选了 u,对应的 dp 数组为
f[u][0/1]
:
那么 v 是由 Alice 选的,于是 Alice 会最大化f[u][0/1]
;
v 之后的一个节点是 Bob 选的,于是 Bob 会最小化从 v 开始的链,则取到最小值f[v][2]
,再加上 v 的值val[v]
;
则f[u][0/1]
分别保存了f[v][2]+val[v]
的最大值和次大值。
具体像下面这样:
1 | for(TNODE *it=T_[u];it;it=it->nxt){ |
要特殊处理叶子节点,把它的 f[u][0]
和 f[u][2]
赋为 0。
然后就要计算 g[u][..]
了,这个就不需要最小和次小了,只计算:
g[u][0]
表示 Alice 选点 u 时,Bob 选 u 的父亲,然后往上找链得到的最小值;g[u][1]
表示 Bob 选点 u 时,Alice 选 u 的父亲,往上找链得到的最大值;
然后考虑从 g[u][..]
怎么计算 g[v][..]
:
如果 Alice 选 v,那么 u 是 Bob 选的,u 之后的点是 Alice 选的:
于是 Alice 会最大化 u 开始往上的链,要么是
g[u][1]+val[u]
,要么是f[u][0/1]+val[u]
;比如这样(u 是 Bob 选的,绿色点是由 Alice 决定的):
反过来,如果 Bob 选 v,那么 u 是 Alice 选的,u 之后的点是 Bob 选:
于是 Bob 会最小化从 u 开始往上的链,要么是
g[u][0]+val[u]
要么是f[u][2/3]+val[u]
;同理嘛……
但是默认的根节点 1 比较特殊,因为它不存在向上的链,那么 g[1][..]
就没有定义,特别讨论一下即可。
1 | //gA 表示 u 是 Alice 选的,即 g[u][0];gB 则是 g[u][1] |
最后就要统计答案了,可能有以下几种情况:
对于一般的节点,如果它是 Alice 开局选的节点,那么 Bob 会从可取的方案中,选取到
min(g[u][0],f[u][2])+val[u]
:对于根节点,没有
g[u][0]
;对于叶子节点,没有
f[u][2]
;
是不是很简单?(反正我觉得是真的绕,尤其是 max 和 min……)
Part3. 源代码
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
写了恶心题没有心情写题了……写篇博客调整心态 :)