方法思路

1. 输入处理：读取节点数量、节点权值、树的边以及查询区间 [l, r]。
2. 树的构建：使用邻接表表示树结构，其中每个节点存储其子节点列表。
3. 深度优先搜索（DFS）：从根节点开始遍历树，维护当前路径的二进制数值。每当到达叶子节点时，检查该数值是否在给定区间内，若在则增加结果计数。
4. 二进制数值处理：在遍历过程中，通过左移和按位或操作动态计算路径的二进制数值，确保高效处理。

这种方法确保所有可能的根到叶子的路径都被检查，从而统计满足条件的路径数目。

代码实现

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] values = new int[n + 1];
        String[] valuesStr = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            values[i] = Integer.parseInt(valuesStr[i-1]);
        }
        
        List<Integer>[] tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < n - 1; i++) {
            String[] edge = br.readLine().split(" ");
            int u = Integer.parseInt(edge[0]);
            int v = Integer.parseInt(edge[1]);
            tree[u].add(v);
        }
        
        String[] limits = br.readLine().split(" ");
        long l = Long.parseLong(limits[0]);
        long r = Long.parseLong(limits[1]);
        
        // 使用数组存储结果，避免使用全局变量
        int[] result = new int[1];
        
        dfs(1, 0L, tree, values, l, r, result);
        
        System.out.println(result[0]);
    }
    
    private static void dfs(int node, long pathValue, List<Integer>[] tree, int[] values, long l, long r, int[] result) {
        // 更新路径值
        pathValue = (pathValue << 1) | values[node];
        
        // 判断是否为叶子节点
        if (tree[node].isEmpty()) {
            if (pathValue >= l && pathValue <= r) {
                result[0]++;
            }
            return;
        }
        
        // 遍历子节点
        for (int child : tree[node]) {
            dfs(child, pathValue, tree, values, l, r, result);
        }
    }
}

Python

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    values = [0] + list(map(int, input().split()))
    
    # 构建有向树
    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        tree[u].append(v)
    
    l, r = map(int, input().split())
    
    # 非递归实现
    count = 0
    stack = [(1, 0)]  # (节点, 当前路径值)
    
    while stack:
        node, path_value = stack.pop()
        path_value = (path_value << 1) | values[node]
        
        # 叶子节点
        if not tree[node]:
            if l <= path_value <= r:
                count += 1
            continue
        
        # 将子节点添加到栈中
        for child in tree[node]:
            stack.append((child, path_value))
    
    print(count)

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> values(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> values[i];
    }
    
    vector<vector<int>> tree(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
    }
    
    long long l, r;
    cin >> l >> r;
    
    int count = 0;
    
    // 使用栈模拟递归，避免函数调用开销
    vector<pair<int, long long>> stack;
    stack.emplace_back(1, 0);
    
    while (!stack.empty()) {
        auto [node, pathValue] = stack.back();
        stack.pop_back();
        
        // 更新路径值
        pathValue = (pathValue << 1) | values[node];
        
        // 判断是否为叶子节点
        if (tree[node].empty()) {
            if (pathValue >= l && pathValue <= r) {
                count++;
            }
            continue;
        }
        
        // 添加所有子节点到栈
        for (int i = tree[node].size() - 1; i >= 0; i--) {
            stack.emplace_back(tree[node][i], pathValue);
        }
    }
    
    cout << count << endl;
    
    return 0;
}