2022-03-20：给定一棵多叉树的头节点head， 每个节点的颜色只会是0、1、2、3中的一种

2022-03-20：给定一棵多叉树的头节点head， 每个节点的颜色只会是0、1、2、3中的一种， 任何两个节点之间的都有路径， 如果节点a和节点b的路径上，包含全部的颜色，这条路径算达标路径， (a -> ... -> b)和(b -> ... -> a)算两条路径。 求多叉树上达标的路径一共有多少？ 点的数量 <= 10^5。

答案2022-03-20：

方法一：自然智慧，所有节点两两对比。 方法二：递归，前缀和+后缀和+位运算。目前是最难的。 当前节点是起点，当前节点是终点。 子节点两两对比。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	root := NewNode(0)
	root.nexts = make([]*Node, 2)
	root.nexts[0] = NewNode(1)
	root.nexts[1] = NewNode(2)
	root.nexts[0].nexts = make([]*Node, 1)
	root.nexts[0].nexts[0] = NewNode(3)
	ret := colors3(root)
	fmt.Println(ret)
}

type Node struct {
	color int
	nexts []*Node
}

func NewNode(c int) *Node {
	ans := &Node{}
	ans.color = c
	ans.nexts = make([]*Node, 0)
	return ans
}

type Info struct {
	// 我这棵子树，总共合法的路径有多少？
	all int
	// 课上没有强调！但是请务必注意！
	// 一定要从头节点出发的情况下！
	// 一定要从头节点出发的情况下！
	// 一定要从头节点出发的情况下！
	// 走出来每种状态路径的条数
	colors []int
}

func NewInfo() *Info {
	ans := &Info{}
	ans.all = 0
	ans.colors = make([]int, 16)
	return ans
}

func colors3(head *Node) int {
	if head == nil {
		return 0
	}
	return process3(head).all
}

var consider = [][]int{{}, // 0
	{14, 15},                       // 1 -> 0001
	{13, 15},                       // 2 -> 0010
	{12, 13, 14, 15},               // 3 -> 0011
	{11, 15},                       // 4 -> 0100
	{10, 11, 14, 15},               // 5 -> 0101
	{9, 11, 13, 15},                // 6 -> 0110
	{8, 9, 10, 11, 12, 13, 14, 15}, // 7 -> 0111
	{7, 15},                        // 8 -> 1000
	{6, 7, 14, 15},                 // 9 -> 1001
	{5, 7, 13, 15},                 // 10 -> 1010
	{4, 5, 6, 7, 12, 13, 14, 15},   // 11 -> 1011
	{3, 7, 11, 15},                 // 12 -> 1100
	{2, 3, 6, 7, 10, 11, 14, 15},   // 13 -> 1101
	{1, 3, 5, 7, 9, 11, 13, 15},    // 14 -> 1110
	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, // 15 -> 1111
}

func process3(h *Node) *Info {
	ans := NewInfo()
	hs := 1 << h.color
	ans.colors[hs] = 1
	if len(h.nexts) > 0 {
		n := len(h.nexts)
		infos := make([]*Info, n+1)
		for i := 1; i <= n; i++ {
			infos[i] = process3(h.nexts[i-1])
			ans.all += infos[i].all
		}

		lefts := make([][]int, n+2)
		for i := 0; i < n+2; i++ {
			lefts[i] = make([]int, 16)
		}
		for i := 1; i <= n; i++ {
			for status := 1; status < 16; status++ {
				lefts[i][status] = lefts[i-1][status] + infos[i].colors[status]
			}
		}

		rights := make([][]int, n+2)
		for i := 0; i < n+2; i++ {
			rights[i] = make([]int, 16)
		}
		for i := n; i >= 1; i-- {
			for status := 1; status < 16; status++ {
				rights[i][status] = rights[i+1][status] + infos[i].colors[status]
			}
		}
		for status := 1; status < 16; status++ {
			ans.colors[status|hs] += rights[1][status]
		}
		ans.all += ans.colors[15] << 1
		for from := 1; from <= n; from++ {
			for fromStatus := 1; fromStatus < 16; fromStatus++ {
				for _, toStatus := range consider[fromStatus|hs] {
					ans.all += infos[from].colors[fromStatus] * (lefts[from-1][toStatus] + rights[from+1][toStatus])
				}
			}
		}
	}
	return ans
}

执行结果如下：

左神java代码