Java 解法, 执行用时: 387ms, 内存消耗: 22708K, 提交时间: 2023-08-12 12:59:51

import java.util.*;

public class Main {

    static List<Integer>[] g;
    static long l;
    static long r;
    static int n;
    static String str;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        l = sc.nextLong();
        r = sc.nextLong();
        str = sc.next();
        g = new List[n + 1];
        Arrays.setAll(g, v -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            g[x].add(y);
            g[y].add(x);
        }
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dfs(i, -1, 0);
        }
        System.out.println(ans);
    }

    public static long dfs(int cur, int fa, long num) {
        if (num > r) return 0;
        long ans = 0;
        num = num << 1 | (str.charAt(cur - 1) - '0');
        if (fa != -1 && num >= l && num <= r) ans++;
        for (Integer next : g[cur]) {
            if (next != fa) {
                ans += dfs(next, cur, num);
            }
        }
        return ans;
    }
}

Go 解法, 执行用时: 14ms, 内存消耗: 1044K, 提交时间: 2023-08-12 12:59:15

package main

import (
	"bufio"
	. "fmt"
	"os"
)

func main() {
	in, out := bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout)
	var n, l,r,ans int
	var s string
	var x, y int
	Fscan(in, &n, &l, &r, &s)
	g := make([][]int, n+1)
	for i := 0; i < n-1; i++ {
		Fscan(in, &x, &y)
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}

	var dfs func(int, int,int)
	dfs = func(x int, pre int, ret int) {
		
		for _, nxt := range g[x] {
			if nxt !=pre  {
                ret:=ret*2+int(s[nxt-1]-'0')
				if ret >= l && ret <= r {
					ans++
				} else if ret > r {
					return
				}
				dfs(nxt, x, ret)
			}
		}
	}
	for i := 1; i <= n; i++ {
		dfs(i, 0, int(s[i-1]-'0'))
	}
	Fprintln(out, ans)
	defer out.Flush()
}

C++ 解法, 执行用时: 15ms, 内存消耗: 5168K, 提交时间: 2023-08-12 12:58:49

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<long long>h[N];
string s;
long long n,l,r,ans;

void dfs(int u,int fa,long long mid){
	mid=mid*2+s[u-1]-'0';
	if(mid>r)return;
	if(fa&&mid>=l)ans++;
	for(int v:h[u]){
		if(fa==v)continue;
		dfs(v,u,mid);
	}
}

int main(){
	cin>>n>>l>>r>>s;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		h[x].push_back(y);
		h[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	dfs(i,0,0);
	cout<<ans<<endl;
	return 0;
}

Python3 解法, 执行用时: 1760ms, 内存消耗: 5684K, 提交时间: 2023-08-12 12:58:29

n,l , r =map(int, input().split())
s = input()
g = [[] for _ in range(n + 10)]
for i in range(n - 1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

res = 0
st = [False] * (n + 1)
def dfs(u, now):
    global res
    st[u] = True
    now += s[u - 1]
    if len(now) > 1 and l <= int(now,2) <= r:
        
        res += 1
    for p in g[u]:
        if not st[p]:
            dfs(p, now)
    
    
for i in range(n + 1):
    st = [False] * (n + 1)
    dfs(i, '')
print(res)