任意挑一個 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搜尋
: 都不可能是解答。
: 我是不是漏了什麼重要線索？