任意挑一个 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搜寻 : 都不可能是解答。 : 我是不是漏了什麽重要线索？ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 36.231.16.216