题解

题面描述

有一颗装满彩灯的二叉树，树的每个节点代表一个灯泡。每个灯泡有三种颜色状态：红色（用整数$1$表示）、绿色（用整数$2$表示）和蓝色（用整数$3$表示）。每个节点上都配有一个开关，当按下某个节点的开关时，以该节点为根节点的子树上所有节点的灯泡颜色都会根据当前的颜色按照“红 → 绿 → 蓝 → 红 → …”的循环切换顺序切换一次颜色。

给定二叉树的初始颜色状态$initial$和目标颜色状态$target$，两者都以层序遍历的一维整数数组的形式表示，数组元素对应二叉树层序遍历的节点的颜色。如果某个节点在二叉树中不存在，则在数组中使用$0$表示。

目标是计算将二叉树从初始颜色状态$initial$切换到目标颜色状态$target$所需的最少开关切换次数。

思路

我们可以通过深度优先遍历（DFS）的方法，从根节点开始处理每个节点的颜色变化。

每个节点的颜色变换受其父节点的影响，因为父节点的开关操作会影响该节点及其子树的颜色。因此，对于每个节点，我们计算从其当前颜色到目标颜色所需的最小开关次数。

具体步骤如下：

1. 使用深度优先遍历（DFS）遍历二叉树。
2. 每次遍历到一个节点时，判断当前节点的颜色与目标颜色的差异。
3. 如果需要切换颜色，则记录一次操作，并通过递归的方式将影响传播到其子节点。
4. 每次切换开关时，将当前节点的颜色变化传递给其左右子节点，保证子树的颜色也能正确变化。

通过这样的方法，能够确保在最少的开关次数下将所有节点的颜色从$initial$转换为$target$。

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 定义节点数量
int n;
// 定义初始颜色状态数组和目标颜色状态数组
vector<int> a, b;
// 最少开关次数
ll ans = 0;
// 深度优先遍历函数
void dfs(int i, int f) {
    // 如果节点不存在或者超出范围，直接返回
    if (i >= n || a[i] == 0) return;
    // 当前节点的颜色偏移
    int cur = (a[i] - 1 + f) % 3;
    // 计算当前节点到目标颜色所需的切换次数
    int need = (b[i] - 1 - cur + 3) % 3;
    // 累加所需的开关次数
    ans += need;
    // 更新偏移量，将需要的颜色变化传递给子树
    int nf = (f + need) % 3;
    // 递归遍历左子树
    dfs(2 * i + 1, nf);
    // 递归遍历右子树
    dfs(2 * i + 2, nf);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    // 读取节点数
    cin >> n;
    // 初始化数组 a 和 b
    a.resize(n);
    b.resize(n);
    // 读取初始颜色状态数组
    for (int i = 0; i < n; i++) cin >> a[i];
    // 读取目标颜色状态数组
    for (int i = 0; i < n; i++) cin >> b[i];
    // 从根节点开始深度优先遍历，初始偏移量为0
    dfs(0, 0);
    // 输出最少的开关次数
    cout << ans << "\n";
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] a, b;
    static long ans = 0;

    // 深度优先遍历函数
    static void dfs(int i, int f) {
        if (i >= n || a[i] == 0) return;  // 如果当前节点不存在，则返回
        int cur = (a[i] - 1 + f) % 3;  // 计算当前节点的颜色偏移
        int need = (b[i] - 1 - cur + 3) % 3;  // 计算需要的颜色变化
        ans += need;  // 累加所需的开关次数
        int nf = (f + need) % 3;  // 更新偏移量
        dfs(2 * i + 1, nf);  // 递归遍历左子树
        dfs(2 * i + 2, nf);  // 递归遍历右子树
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());  // 读取节点数
        a = new int[n];  // 初始颜色状态
        b = new int[n];  // 目标颜色状态
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());  // 读取初始状态
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) b[i] = Integer.parseInt(st.nextToken());  // 读取目标状态
        dfs(0, 0);  // 从根节点开始深度优先遍历
        System.out.println(ans);  // 输出最少的开关次数
    }
}

Python

import sys
sys.setrecursionlimit(10**7)

# 深度优先遍历函数
def dfs(i, f):
    global ans
    if i >= n or a[i] == 0:  # 如果当前节点不存在，则返回
        return
    cur = (a[i] - 1 + f) % 3  # 计算当前节点的颜色偏移
    need = (b[i] - 1 - cur + 3) % 3  # 计算需要的颜色变化
    ans += need  # 累加所需的开关次数
    nf = (f + need) % 3  # 更新偏移量
    dfs(2*i + 1, nf)  # 递归遍历左子树
    dfs(2*i + 2, nf)  # 递归遍历右子树

def main():
    global n, a, b, ans
    data = sys.stdin.read().split()  # 读取输入
    n = int(data[0])  # 读取节点数
    a = list(map(int, data[1:1+n]))  # 读取初始颜色状态
    b = list(map(int, data[1+n:1+2*n]))  # 读取目标颜色状态
    ans = 0
    dfs(0, 0)  # 从根节点开始深度优先遍历
    print(ans)  # 输出最少的开关次数

if __name__ == "__main__":
    main()

题目内容

假设我们有一颗装满彩灯的二叉树，树的每个节点代表一个灯泡。每个灯泡有三种颜色状态：红色(用整数 $1$ 表示)、绿色(用整数 $2$ 表示)和蓝色(用整数 $3$ 表示)。每个节点上都配有一个开关，当按下某个节点的开关时，以该节点为根节点的子树上所有节点的灯泡颜色都会根据当前的颜色按照 "$红 -> 绿 -> 蓝 -> 红 ->…$"的循环切换顺序切换一次颜色。

给定二叉树的初始颜色状态 initial 和目标颜色状态 target，两者都以层序遍历的一维整数数组的形式表示，数组元素对应二叉树层序遍历的节点的颜色。如果某个节点在二叉树中不存在，则在数组中使用 $0$ 表示。

目标：计算将二叉树从初始颜色状态 initial 切换到目标颜色状态 target 所需的最少开关切换次数。

解释补充：

• “层序遍历"是指从上到下、从左到右逐层遍历二叉树的节点，并将遍历结果保存在一维数组中，如果某个节点在二叉树中不存在，则在数组中使用 $0$ 表示。

• 切换开关的影响是“传递性"的，即切换一个节点的开关会影响以该节点为根节点的子树上所有节点的灯泡颜色。

输入描述

第一行榆入为一个整数n，代表intiamp和largeu的数组大小

第二行输入为n个整数，代表imnitial的元系值

第三行输入为n个整数，target的元系值

参数取值范围:

• $initial.lenght == targets.lenght$

• $0 <= initial[i] <= 3$ ，且为整数

• $0 <= targets[i] <= 3$，且为整数

• 如果 $initial[i] ==0$ ，则 $targets[i] ==0$

• $1 <= initial.lenght <= 10^6$

输出描述

一个整数，表示最少开关切换次数。

样例1

输入

5
1 2 3 0 1
2 3 1 0 2

输出

1

说明

初始状态initial[]为[1，2，3，8，1]，代表二叉树为:

  1
 / \
2   3
 \
  1

切换一次根节点颜色:

    1->2
   / \
2->3  3->1
   \
   1->2

切换后变为:

   2
  / \
 3   1
  \
   2

即为:[2，3，1，8，2]，满足目标状态target[]，总共切换了1次，所以返回为1

样例2

输入

7
1 2 3 1 2 3 1
3 1 2 3 1 2 1

输出

3

说明

初始状态initial[]为[1，2，3，1，2，3，1]，代表树为:

        1
     /    \
    2      3
  /  \    /  \
 1    2  3    1

切换一次根节点变为:

         2
     /      \
    3        1
  /   \    /   \
 2     3  1     2

切换一次根节点变为:

         3
     /      \
    1        2
  /   \    /   \
 3     1  2     3

切换末尾节点一次:

         3
     /      \
    1        2
  /   \    /   \
 3     1  2    3->1

即为:[3，1，2，3，1，2，1]，满足目标状态target[]，总共切换了3次，所以返回为3