为了更好的阅读体检，可以查看我的算法学习网
在线评测链接:P1224

题目内容

很久很久以前，有一个神秘的森林，这个森林里有一棵特殊的树，它被称为“魔法之树”。这棵树的每个节点都有一个权值，为 $0$ 或 $1$，而且它们之间存在着连接，形成了一颗有 $n$ 个节点的二叉树。

人们相信，这棵树里蕴含着无穷的魔法力量，因为每一条路径都可以被看作是一串二进制数，而这些二进制数可以组成无数的数字，代表着神秘的力量和秘密。

为了探寻这个魔法之树的秘密，有许多勇敢的冒险家来到这个森林，试图通过对这棵树的研究来揭示其神秘力量的本质。然而，他们面临的问题是，有多少条路径代表的二进制数在 $[l,r]$ 区间范围内？

塔子哥是一个来自遥远国度的数学家，他擅长解决这种数字问题。他在研究这棵树的过程中，发现了一种高效的算法，可以帮助寻找树中所有代表的二进制数，并且得到有多少条路径代表的二进制数在 $[l,r]$ 区间范围内？他希望你能帮助他实现这个算法，为神秘的魔法之树揭开更多的秘密。

(请注意: 路径长度至少为 $1$ ，例如，节点 $3$ 到节点 $3$ 虽然有一个权值，但并不是合法路径！)

输入描述

第一行输人三个正整数 $n$ ， $l$ ， $r$ ，用空格隔开。

第二行输入一个长度为 $n$ 的 01 串，第 $i$ 个字符代表 $i$ 号节点的权值。

接下来的 $n-1$ 行，每行输入两个正整数 $u$ 和 $v$ ，代表 $u$ 号节点和 $v$ 号节点有一条边连接。

$1\le n\le 10^3$ ， $1\le u,v\le n$ ， $1\le l\le r\le 10^{14}$

输出描述

一个整数，代表合法的路径条数。

样例

输入

5 2 5
11010
1 2
1 3
2 4
2 5

输出

9

思路：DFS

因为给定的树最多只有$1000$个节点，所以我们可以通过枚举每个节点作为起点来解决这个问题。我们将使用深度优先搜索$（DFS）$来遍历以每个起点为根的子

树，并计算沿着路径的二进制数的值。在这个过程中，我们会检查计算得到的二进制数是否处于给定的区间范围$[l,r]$之间。如果是，我们将答案计数器加一，

表示找到了一个满足条件的路径。

我们递归地调用$DFS$函数来处理当前节点的左子节点和右子节点。在递归调用中，我们更新当前路径的二进制数值，将其左移一位（表示加上左子节点的权

值）或左移一位再加一（表示加上右子节点的权值）。

代码

CPP

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 1010;
vector<int> g[N];
int n;
ll l, r;
char s[N];
int ans;void dfs(int cur, int u, int fa, ll val) {val = val * 2 + (s[u] - '0');if (val > r) return ;if (val >= l && u != cur) ans += 1;for (int v: g[u]) {if (v == fa) continue ;dfs(cur, v, u, val);}
}void solve() {scanf("%d%lld%lld", &n, &l, &r);scanf("%s", s + 1);for (int i = 1; i < n; ++i) {int a, b;scanf("%d%d", &a, &b);g[a].push_back(b);g[b].push_back(a);}ans = 0;for (int i = 1; i <= n; ++i) {dfs(i, i, 0, 0);}printf("%d\n", ans);
}int main()
{int T = 1;
//    scanf("%d", &T);while (T--) {solve();}return 0;
}

python

import sys
sys.setrecursionlimit(200000)n, L, R = map(int, input().split())
ss = input()
a = [1 if ss[i]=='1' else 0 for i in range(n)]
e = [[] for i in range(n)]
for i in range(n-1):x, y = map(int, input().split())e[x-1].append(y-1)e[y-1].append(x-1)ans = 0
def dfs(s, fa, v):global ansif fa != -1 and L <= v <= R:ans += 1if v > R:returnfor t in e[s]:if t == fa:continuedfs(t, s, v<<1|a[t])
for i in range(n):dfs(i, -1, a[i])
print(ans)

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static int n;static long l, r;static char[] s;static List<List<Integer>> g;static int ans;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();l = scanner.nextLong();r = scanner.nextLong();s = new char[n + 1];g = new ArrayList<>();for (int i = 0; i <= n; i++) {g.add(new ArrayList<>());}String inputString = scanner.nextLine(); inputString = scanner.nextLine();for (int i = 1; i <= n; i++) {s[i] = inputString.charAt(i - 1);}for (int i = 1; i < n; i++) {int a = scanner.nextInt();int b = scanner.nextInt();g.get(a).add(b);g.get(b).add(a);}scanner.close();ans = 0;for (int i = 1; i <= n; i++) {dfs(i, i, 0, 0);}System.out.println(ans);}public static void dfs(int cur, int u, int fa, long val) {val = val * 2 + (s[u] - '0');if (val > r)return;if (val >= l && u != cur)ans++;for (int v : g.get(u)) {if (v == fa)continue;dfs(cur, v, u, val);}}
}

Go

package mainimport ("bufio""fmt""os""strconv""strings"
)var n int
var l, r int64
var s []byte
var g [][]int
var ans intfunc main() {scanner := bufio.NewScanner(os.Stdin)// Read and parse n, l, rscanner.Scan()fields := strings.Fields(scanner.Text())n, _ = strconv.Atoi(fields[0])l, _ = strconv.ParseInt(fields[1], 10, 64)r, _ = strconv.ParseInt(fields[2], 10, 64)// Allocate space for s and gs = make([]byte, n+1)g = make([][]int, n+1)for i := 1; i <= n; i++ {g[i] = []int{}}// Read sscanner.Scan()copy(s[1:], scanner.Text())// Read edgesfor i := 1; i < n; i++ {scanner.Scan()fields = strings.Fields(scanner.Text())a, _ := strconv.Atoi(fields[0])b, _ := strconv.Atoi(fields[1])g[a] = append(g[a], b)g[b] = append(g[b], a)}ans = 0for i := 1; i <= n; i++ {dfs(i, i, 0, 0)}fmt.Println(ans)
}func dfs(cur, u, fa int, val int64) {val = val*2 + int64(s[u]-'0')if val > r {return}if val >= l && u != cur {ans++}for _, v := range g[u] {if v == fa {continue}dfs(cur, v, u, val)}
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {input += data;
});
process.stdin.on('end', () => {let lines = input.trim().split('\n');let [n, l, r] = lines[0].split(' ').map(Number);let s = ['0'].concat(lines[1].split(''));let g = Array.from({length: n+1}, () => []);for(let i = 2; i < n + 1; i++){let [a, b] = lines[i].split(' ').map(Number);g[a].push(b);g[b].push(a);}let ans = 0;for(let i = 1; i <= n; i++){dfs(i, i, 0, 0);}console.log(ans);function dfs(cur, u, fa, val){val = val * 2 + Number(s[u]);if(val > r) return;if(val >= l && u !== cur) ans++;for(let v of g[u]){if(v === fa) continue;dfs(cur, v, u, val);}}
});

题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除。