← 返回题目列表

Codeforces · 1326/G

G. 蜘蛛网树

中文机器翻译题面 查看原题

让我们调用一个具有 $$$n$$$ 顶点的图,每个顶点都有自己的点 $$$A_i = (x_i, y_i)$$$ 具有整数坐标,平面树如果:

- 所有点 $$$A_1、A_2、\ldots、A_n$$$ 都不同,并且没有三个点位于同一条线上。
- 该图是一棵树,即恰好有 $$$n-1$$$ 边,任何一对顶点之间都存在路径。
- 对于所有边对 $$$(s_1, f_1)$$$ 和 $$$(s_2, f_2)$$$,使得 $$$s_1 \neq s_2, s_1 \neq f_2,$$$ $$$f_1 \neq s_2$$$ 和 $$$f_1 \neq f_2$$$,段$$$A_{s_1} A_{f_1}$$$ 和 $$$A_{s_2} A_{f_2}$$$ 不相交。

想象一棵具有 $$$n$$$ 个顶点的平面树。考虑点 $$$A_1, A_2, \ldots, A_n$$$ 的凸包。如果对于所有 $$$1 \leq i \leq n$$$ 下列陈述成立,我们称这棵树为蜘蛛网树:

- 树的所有叶子(度数 $$$\leq 1$$$ 的顶点)位于凸包的边界上。
- 凸包边界上的所有顶点都是叶子。

蜘蛛网树的示例:

点 $$$A_3, A_6, A_7, A_4$$$ 位于凸包上,树的叶顶点是 $$$3, 6, 7, 4$$$。

请参阅注释以获取更多示例。

如果对于 $$$S$$$ 中的所有顶点对,存在一条仅包含来自 $$$S$$$ 的顶点的路径,我们将顶点的子集 $$$S \subset \{1, 2, \ldots, n\}$$$ 称为树的子树。请注意,平面树的任何子树都是平面树。

给你一棵有 $$$n$$$ 个顶点的平面树。我们将集合 $$$\{1, 2, \ldots, n\}$$$ 划分为非空子集 $$$A_1, A_2, \ldots, A_k$$$ (即 $$$A_i \cap A_j = \emptyset$$$ 对于所有 $$$1 \leq i < j \leq k$$$ 和 $$$A_1 \cup A_2 \cup \ldots \cup A_k = \{1, 2, \ldots, n\}$$$) 如果对于所有 $$$1 \leq i \leq k$$$,子树 $$$A_i$$$ 是一棵蜘蛛网树,那就很好。如果一个分区中存在某个集合,而另一个分区中不存在,则两个分区是不同的。

查找良好分区的数量。由于这个数字可能非常大,因此请对 $$$998\,244\,353$$$ 求模。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 树中的顶点数。

接下来的 $$$n$$$ 行每行包含两个整数 $$$x_i, y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — 第 $$$i$$$ 个顶点的坐标 $$$A_i$$$。

接下来的 $$$n-1$$$ 行包含两个整数 $$$s, f$$$ ($$$1 \leq s, f \leq n$$$) - 树的边 $$$(s, f)$$$。

保证所有给定的点都不同,并且没有三个点位于同一条线上。此外,保证给定的边和点的坐标描述平面树。

输出

打印一个整数 - 给定平面树的顶点的良好分区数,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

4
0 0
0 1
-1 -1
1 -1
1 2
1 3
1 4

输出 #1

5

输入 #2

5
3 2
0 -3
-5 -3
5 -5
4 5
4 2
4 1
5 2
2 3

输出 #2

8

输入 #3

6
4 -5
0 1
-2 8
3 -10
0 -1
-4 -5
2 5
3 2
1 2
4 6
4 2

输出 #3

13

输入#4

8
0 0
-1 2
-2 5
-5 1
1 3
0 3
2 4
-1 -4
1 2
3 2
5 6
4 2
1 5
5 7
5 8

输出#4

36

注意

第一个样本的图片。

在第一个测试用例中,所有好的分区是:

1. $$$\{1\}$$$, $$$\{2\}$$$, $$$\{3\}$$$, $$$\{4\}$$$;
2. $$$\{1, 2\}$$$, $$$\{3\}$$$, $$$\{4\}$$$;
3. $$$\{1, 3\}$$$, $$$\{2\}$$$, $$$\{4\}$$$;
4. $$$\{1, 4\}$$$, $$$\{2\}$$$, $$$\{3\}$$$;
5. $$$\{1, 2, 3, 4\}$$$.

分区 $$$\{1, 2, 3\}$$$, $$$\{4\}$$$ 不好,因为子树 $$$\{1, 2, 3\}$$$ 不是蜘蛛网树,因为非叶顶点 $$$1$$$ 位于凸包上。

分区 $$$\{2, 3, 4\}$$$, $$$\{1\}$$$ 不好,因为子集 $$$\{2, 3, 4\}$$$ 不是子树。

第二个示例的图片。

在第二个测试用例中,给定的树不是蜘蛛网树,因为叶顶点 $$$1$$$ 并不位于凸包上。然而,子树 $$$\{2, 3, 4, 5\}$$$ 是一棵蜘蛛网树。

第三个样本的图片。

第四个样本的图片。

在第四个测试用例中,分区 $$$\{1, 2, 3, 4\}$$$, $$$\{5, 6, 7, 8\}$$$ 很好,因为所有子集都是蜘蛛网子树。