D2T1

图中不存在横插边，$u \rightsquigarrow v$ 可拆成 $u \rightsquigarrow \operatorname{lca}(u, v) \rightsquigarrow v$ 计算。 对 $u \rightsquigarrow \operatorname{lca}(u, v ......

# NOIP2014 奶酪 ## 题面： NOIP2014 提高组 D2T1 现有一块大奶酪，它的高度为 $h$，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 $z = 0$，奶酪的上表面为 $z = h$。 ......

## Problem 一个共 $n$ 层的内向满二叉树，给定 $m$ 个前向边（即往子树走的边），边有非负权，问所有可以从 $u$ 通向 $v$ 的点对 $(u,v)$ 的最短路长度之和。$n\le18$，$m\le2\times10^5$。 ## Preface D1T1 是我基本上独立想出的，这 ......

我们可以先 $dp$，设 $f_{i,j,k,l}$ 和 $g_{i,j,k,l}$表示当前三个棋子分别在点 $i,j,k$，目前轮到 $l$ 走，谁胜利，最终会走多少步。 然后我们发现，变成一个有向图博弈。并且 $l$ 是由 $i,j,k$ 的奇偶性唯一确定的。就可以在图上直接做了。 首先我们发现 ......