任意挑一个 leaf 当作 root 把这棵树挂起来
扣掉这个 root 之后 下面会是 full binary tree
也就是除了 leaf 之外每个点都有 2 个小孩
假设 B,C 是 leaves, A 是他们的 parent
加上那 k 条边之后会从左边的图变成右边
| |
A A
/ \ / \
B C -B-C-
这个结构其实对任意的 sub-tree 都是通用的
A 是 root, B 和 C 是 A 下面的 sub-tree
我们可以利用这个结构来做归纳
先看一个 leaf 的状况
|
-B-
一个 Hamilton Circuit 一定会通过 {上,左,右} 三条边中的恰好两条
| | |
-B- -B- -B-
对 B 来说 {上左}, {上右}, {左右} 各有 1 种可能
再看 A 是 root, B 和 C 是 sub-tree 的状况
| | |
A A A
/ \ / \ / \
-B-C- -B-C- -B-C-
(a) (b) (c)
(a) 如果 B 选 {上左}，那 C 就一定要 {上右}，整个 A sub-tree 就是 {左右}
(b) 如果 B 选 {上右}，那 C 就一定要 {左右}，整个 A sub-tree 就是 {上左}
(c) 如果 B 选 {左右}，那 C 就一定要 {上左}，整个 A sub-tree 就是 {上右}
如果不是这三种情形，就一定连不成 Hamilton circuit
在这三种情形中 我们都可以把整个 A sub-tree 缩成一个点
来继续推论 A 的 parent 和 sibling 要选哪些边进 Hamilton circuit
(B -> A 和 A sub-tree -> parent(A) 的关系一样)
简而言之 一旦 B 的边决定了 C 和 A 的边也就跟着决定了
更进一步说 一旦 A sub-tree 的边决定了 A 的 parent 的边也就决定了
也就是整棵树的 Hamilton circuit 就决定了!!
所以其实无论 N 多大 答案都是 3
理由是第一个叶子(上面的B)有三种选边的方法
而这个叶子每一种方法都可以推出一个 Hamilton circuit (也只会推出一个)
那题目说的线性复杂度要用在哪里?
用在检查 input 是不是符合规定的图
题目叙述有说可能会有不合规定的 input 这时候要输出 -2
在 Codility 的 demo: https://codility.com/demo/results/demoAB76TX-6HV/
检查 input 写得很丑请见谅
※ 引述《FRAXIS (喔喔)》之铭言：
: 我在尝试解Codility上面 Eta 2011的问题
: http://codility.com/train/
: 题目的大意是这样，给定一个m个顶点的unrooted binary tree，m为偶数。
: （原题是说图上有两种节点，一种节点degree为3，另一种节点degree为1，
: 而且边数只有 m - 1，所以应该就是unrooted binary tree）
: 然后给一个从树上一点出发的in-order traversal order。
: 令所有leaves在此order出现的顺序为 l1, l2, ..., lk, k为leaf的个数。
: 接着在树上增加k条边，分别是 (l1, l2), (l2, l3), ..., (lk-1, lk), (lk, l1)
: （原题是给你一个tour，每条边都被visit两次，degree为1的点被visit一次，
: degree为3的点被visit 3次，依照degree为1的点被visit的顺序，建立一个cycle去
: 连接这些degree为1的点）
: 问在此图上有多少条Hamiltonian Circuit。
: 虽然我可以知道这个图是3-regular，同时也是planar，但是好像对于找出
: Hamiltonian Circuit的数量没有太大帮助。
: 而且题目的时间复杂度要求为线性，所以复杂度高的图论算法或是Heuristic搜寻
: 都不可能是解答。
: 我是不是漏了什么重要线索？