2 月 14 日 Codeforces Global Round 1
题目链接:https://codeforces.com/contest/1110

F – Nearest Leaf

思路:

考虑用线段树维护当前点到叶子节点的距离,那么对于询问就是查询区间最小值。我们从根节点开始,按照 dfs 序依次维护在每一个点上的线段树。当从点 $x$ 走到点 $son_x$ 且边权为 $dis$ 时,$son_x$ 子树内点的距离减少了 $dis$,其余点点距离增加了 $dis$,由于一棵子树的 dfs 序是连续的,因此就对应于线段树的区间修改。

代码链接

G – Tree-Tac-Toe

思路:

首先发现黑色是不可能赢的。为了简化情况,我们先假设所有点都是没有涂色的,然后考虑有哪些情况白色必定赢。比较简单的一种就是存在度数大于 4 的节点,然后发现如果一个点度数为 3 且有两个相邻的非叶节点时,白色也同样必胜。排除掉这两种情况后,剩下的树的形态就比较简单了。如下图一样,就是中间一条长链,两端可能会有度数为 3 的点,当然也可能没有度数为3的点。

Tree-Tac-Toe 1

然后考虑这种情况下白色怎样才能获胜,可以发现只有两端都有度数为 3 的端点且链长为偶数时,白色才能获胜。然后其余的所有情况都会是平局。

如果一开始树上有些点已经是白色了,考虑如何处理这种情况。比较巧妙的方式就是将一个白点按照下图的方式,拆成 4 个无色的点,可以发现这两种是完全等价的。然后就按照开始所讲的情况进行讨论即可。

Tree-Tac-Toe 2

代码链接

发表评论

邮箱地址不会被公开。 必填项已用*标注