Vlak
题面
Nina 和 Emilija 轮流写字母 , 每个人写下的字母后的总字符串必须是对方指定的字符串的前缀 . 无法写下字母是对方获胜 .
每个人都会采取最优策略 .
解题思路
字典树加一点点贪心 .
首先将 Tire 树建好 , 另外记录每条边的所属信息 ( Nina 或 Emilija ) . 树上 $Dfs$ 即可 .
$Dfs$ 具体思路 :
把当前选择写字母的人的过程转换为当前点找边 , 点的深度表示当前写字母的人 ( 0 代表 Nina , 1 代表 Emilija ) , 只搜索属于自己的边 .
Strategy 1
向下找边时 , Nina 找到一条尽属于她自己的边 , 则当前的最优解就是选这条边 . 当下一次 Emilija 进行选边是一定无边可选 . Nina 获胜 .
Strategy 2
如果 Nina 找不到属于她自己的边 , 就无法向下找边 , Emilija 获胜 .
Strategy 3
如果 Nina 找到了属于她们两人的边 , 直接 $Dfs$ 都试一下 , 只要有一条能使她必胜 , 那么这条边就是所有的最优策略 . 否则 Emilija 必胜 .
总而言之 , 如果一条边同时属于两个人 , 向下把每条边 $Dfs$ , 只要有一条边的返回值能使她必胜那么对手必输 , 反之亦然 .
Papričice
题面
有 $n$ 个节点 ( 辣椒 ) , 这些节点由 $n - 1$ 条边连起来组成一棵树 . 现在需要删除 ( 切掉 ) 2 条边 , 使得这棵树分为 3 个子树 , 每个子树内节点的数量分别为 $a , b , c$ . 求 $\min(\max{(a,b,c)} - \min{(a,b,c)})$ .
解题思路
设节点 1 为根节点 , $size_i$ 为以 $i$ 为根的子树的节点的个数 , 则只有两种可以切割的情况 :
1 . 所切下来的 2 个节点以 $u$ , $v$ 为根 , 且互不为对方的祖先 , 则这 3 棵子树内的节点数分别为 $size_u$ , $size_v$ , $n - size_u - size_v$
对于这种情况 , 枚举其 LCA 的节点 $p$ . 在 $p$ 中的子树集合找到 $2$ 个集合最接近 $\dfrac{n}{3}$ 就 $o$ 的 $k$ 了 . ヾ(≧▽≦*)o
2 . 另一种情况是第 $1$ 刀切的边是 $u$ 的子树, 第 $2$ 刀切的是 $u$ 中的一个节点 $v$ 和它的父节点的边 . 则这 $3$ 棵子树内的节点数分别为 $size_u - size_v$ , $size_v$ , $n - size_u$ .
这种情况直接枚举所有 $u$ . 在集合内找最接近 $\dfrac{size_u}{2}$ 的子树 .
复杂度 $O(n \log^2 n)$