REALHW86 荧光森林的共鸣路径

题目链接

荧光森林的共鸣路径

题目描述

在一片神秘的荧光森林中，生长着一种名为“辉光之树”的奇特植物。这些植物的根系在地底深处交织成一张巨大的网络，形成了一棵宏伟的二叉树结构。每株植物都是树上的一个节点，并且自身储存着一定的能量。

作为一名探索这片森林的植物学家，您发现当能量以一种特定的“之字形”模式在植物间传导时，会引发壮观的“能量共鸣”现象。您的任务是找出这片森林中所有可能形成的、总能量值恰好等于特定值的共鸣路径。

给定一个由 $N$ 株荧光植物构成的二叉树，以及一个目标能量值 $target$ 。您需要计算出满足以下条件的 共鸣路径 的总数量。

路径 (Path): 一条有效的路径必须从树中的任意一个节点开始，并一直延伸到某个 叶子节点（没有子节点的植物）结束。
共鸣路径 (Resonance Path): 一条路径要被称为“共鸣路径”，其上的节点序列必须遵循“之字形”的能量传导规则，并且路径长度至少为3。规则如下：
1. 从父节点到第一个子节点的方向是任意的（左或右）。
2. 此后，能量的传导方向必须严格交替。即，如果上一步是“父 -> 左子”，则下一步必须是“当前 -> 右子”；如果上一步是“父 -> 右子”，则下一步必须是“当前 -> 左子”。

任务目标: 找出所有满足“路径上所有植物的能量值之和等于目标能量 $target$ ”的 共鸣路径 的数量。

解题思路

这是一个典型的在二叉树中寻找满足特定条件的路径数量的问题，可以通过深度优先搜索（DFS）来解决。由于路径可以从任意节点开始，我们需要遍历树中的每一个节点，并以它为起点进行搜索。

1. 预处理与特殊情况

建树：输入给的是一个层序遍历的数组，我们可以利用数组下标直接模拟树的结构，即对于节点 i，其左子节点为 2*i + 1，右子节点为 2*i + 2。值为 -1 的节点表示空节点。
特殊情况：题目要求共鸣路径的长度至少为 3，且必须是“之字形”。因此，在开始搜索前，我们必须检查树中是否存在至少一条长度为3的“之字形”路径。这等价于检查是否存在任何节点 i 满足以下任一条件：
1. i 的左子节点存在，且该左子节点的右子节点也存在 (i -> left -> right)。
2. i 的右子节点存在，且该右子节点的左子节点也存在 (i -> right -> left)。如果不存在这样的结构，那么就不可能形成任何共鸣路径，我们应根据题意直接输出 -1。

2. 深度优先搜索（DFS）

我们将设计一个 DFS 函数来探索所有可能的“之字形”路径。

主循环：我们需要一个外层循环，遍历从 0 到 N-1 的所有节点。如果节点有效（能量值不为 -1），就以该节点作为路径的起点开始 DFS。
启动 DFS：从一个起始节点 start_node 出发，路径可以向左走，也可以向右走。因此，我们会启动两个独立的 DFS 过程：
1. start_node -> left_child -> ...
2. start_node -> right_child -> ...
递归函数设计：我们的核心 dfs 函数需要携带以下信息（状态）：
- u：当前节点的索引。
- currentSum：从路径起点到当前节点的能量总和。
- nextDirection：下一步必须前进的方向（例如，1 代表左，2 代表右）。
- pathLength：当前路径的长度（包含的节点数）。
递归逻辑：
1. 终止条件（Base Case）：当 DFS 到达一个叶子节点时，递归终止。此时，我们检查路径是否满足条件：
  - 路径长度 pathLength 是否 >= 3？
  - 能量总和 currentSum 是否 == target？
  - 如果都满足，则将全局计数器加一。
2. 递归步骤：如果当前节点不是叶子节点，根据 nextDirection 的要求，向左或向右移动到下一个节点。例如，如果 nextDirection 要求向右，我们就递归调用 dfs(right_child, newSum, "向左", newLength)，更新能量和、路径长度，并将下一次要求的方向切换为相反方向。

通过这种方式，我们可以系统地遍历从每个节点出发的所有可能的“之字形”路径，并统计出满足条件的路径总数。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int n;
long long target;
vector<long long> nodes;
int count_paths = 0;

// u: 当前节点索引
// currentSum: 当前路径能量和
// nextDirection: 1-左, 2-右
// pathLength: 当前路径长度
void dfs(int u, long long currentSum, int nextDirection, int pathLength) {
    if (u >= n || nodes[u] == -1) {
        return;
    }

    currentSum += nodes[u];
    pathLength++;

    int leftChild = 2 * u + 1;
    int rightChild = 2 * u + 2;

    bool isLeaf = true;
    if (leftChild < n && nodes[leftChild] != -1) {
        isLeaf = false;
    }
    if (rightChild < n && nodes[rightChild] != -1) {
        isLeaf = false;
    }

    if (isLeaf) {
        if (pathLength >= 3 && currentSum == target) {
            count_paths++;
        }
        return;
    }

    if (nextDirection == 1) { // 必须向左走
        dfs(leftChild, currentSum, 2, pathLength);
    } else { // 必须向右走
        dfs(rightChild, currentSum, 1, pathLength);
    }
}

bool hasZigZagPathLength3() {
    for (int i = 0; i < n; ++i) {
        if (nodes[i] == -1) continue;
        
        // Check for path: i -> left -> right
        int left = 2 * i + 1;
        if (left < n && nodes[left] != -1) {
            int grandRightFromLeft = 2 * left + 2;
            if (grandRightFromLeft < n && nodes[grandRightFromLeft] != -1) {
                return true;
            }
        }

        // Check for path: i -> right -> left
        int right = 2 * i + 2;
        if (right < n && nodes[right] != -1) {
            int grandLeftFromRight = 2 * right + 1;
            if (grandLeftFromRight < n && nodes[grandLeftFromRight] != -1) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n;
    nodes.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> nodes[i];
    }
    cin >> target;

    if (!hasZigZagPathLength3()) {
        cout << -1 << endl;
        return 0;
    }

    for (int i = 0; i < n; ++i) {
        if (nodes[i] != -1) {
            // 启动DFS: 路径从 i -> left_child 开始
            dfs(2 * i + 1, nodes[i], 2, 1);
            // 启动DFS: 路径从 i -> right_child 开始
            dfs(2 * i + 2, nodes[i], 1, 1);
        }
    }

    cout << count_paths << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    static int n;
    static long target;
    static long[] nodes;
    static int countPaths = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        nodes = new long[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = sc.nextLong();
        }
        target = sc.nextLong();

        if (!hasZigZagPathLength3()) {
            System.out.println(-1);
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (nodes[i] != -1) {
                // 启动DFS: 路径从 i -> left_child 开始
                dfs(2 * i + 1, nodes[i], 2, 1);
                // 启动DFS: 路径从 i -> right_child 开始
                dfs(2 * i + 2, nodes[i], 1, 1);
            }
        }

        System.out.println(countPaths);
    }

    // u: 当前节点索引
    // currentSum: 当前路径能量和
    // nextDirection: 1-左, 2-右
    // pathLength: 当前路径长度
    private static void dfs(int u, long currentSum, int nextDirection, int pathLength) {
        if (u >= n || nodes[u] == -1) {
            return;
        }

        currentSum += nodes[u];
        pathLength++;

        int leftChild = 2 * u + 1;
        int rightChild = 2 * u + 2;

        boolean isLeaf = true;
        if (leftChild < n && nodes[leftChild] != -1) {
            isLeaf = false;
        }
        if (rightChild < n && nodes[rightChild] != -1) {
            isLeaf = false;
        }

        if (isLeaf) {
            if (pathLength >= 3 && currentSum == target) {
                countPaths++;
            }
            return;
        }

        if (nextDirection == 1) { // 必须向左走
            dfs(leftChild, currentSum, 2, pathLength);
        } else { // 必须向右走
            dfs(rightChild, currentSum, 1, pathLength);
        }
    }

    private static boolean hasZigZagPathLength3() {
        for (int i = 0; i < n; i++) {
            if (nodes[i] == -1) continue;

            // Check for path: i -> left -> right
            int left = 2 * i + 1;
            if (left < n && nodes[left] != -1) {
                int grandRightFromLeft = 2 * left + 2;
                if (grandRightFromLeft < n && nodes[grandRightFromLeft] != -1) {
                    return true;
                }
            }

            // Check for path: i -> right -> left
            int right = 2 * i + 2;
            if (right < n && nodes[right] != -1) {
                int grandLeftFromRight = 2 * right + 1;
                if (grandLeftFromRight < n && nodes[grandLeftFromRight] != -1) {
                    return true;
                }
            }
        }
        return false;
    }
}

def solve():
    n = int(input())
    nodes_str = input().split()
    nodes = [int(x) for x in nodes_str]
    target = int(input())

    count_paths = 0

    def has_zig_zag_path_length_3():
        for i in range(n):
            if nodes[i] == -1:
                continue
            
            # Check for path: i -> left -> right
            left = 2 * i + 1
            if left < n and nodes[left] != -1:
                grand_right_from_left = 2 * left + 2
                if grand_right_from_left < n and nodes[grand_right_from_left] != -1:
                    return True
            
            # Check for path: i -> right -> left
            right = 2 * i + 2
            if right < n and nodes[right] != -1:
                grand_left_from_right = 2 * right + 1
                if grand_left_from_right < n and nodes[grand_left_from_right] != -1:
                    return True
        return False

    if not has_zig_zag_path_length_3():
        print(-1)
        return

    def dfs(u, current_sum, next_direction, path_length):
        nonlocal count_paths
        if u >= n or nodes[u] == -1:
            return

        current_sum += nodes[u]
        path_length += 1

        left_child = 2 * u + 1
        right_child = 2 * u + 2
        
        is_leaf = True
        if left_child < n and nodes[left_child] != -1:
            is_leaf = False
        if right_child < n and nodes[right_child] != -1:
            is_leaf = False

        if is_leaf:
            if path_length >= 3 and current_sum == target:
                count_paths += 1
            return

        if next_direction == 1:  # 必须向左走
            dfs(left_child, current_sum, 2, path_length)
        else:  # 必须向右走
            dfs(right_child, current_sum, 1, path_length)

    for i in range(n):
        if nodes[i] != -1:
            # 启动DFS: 路径从 i -> left_child 开始
            dfs(2 * i + 1, nodes[i], 2, 1)
            # 启动DFS: 路径从 i -> right_child 开始
            dfs(2 * i + 2, nodes[i], 1, 1)

    print(count_paths)

solve()

算法及复杂度

算法: 深度优先搜索（DFS）
时间复杂度: $O(N^2)$ 。在最坏的情况下（例如，一个链状的树），从每个节点开始的 DFS 都可能遍历接近 $N$ 个节点。由于我们需要从所有 $N$ 个节点启动搜索，总时间复杂度为 $O(N \cdot N) = O(N^2)$ 。hasZigZagPathLength3 函数的复杂度为 $O(N)$ ，不影响总体复杂度。
空间复杂度: $O(N)$ 。空间开销主要来自于递归调用的栈深度。在最坏情况下（一个链状的树），递归深度可能达到 $N$ ，因此空间复杂度为 $O(N)$ 。

题解 | #荧光森林的共鸣路径#