题目如下：
游游拿到了一棵树，有n个节点，每个节点有一个权值0或1。这样每条路径就代表了一个二进制数。
游游想知道，有多少条路径代表的二进制数在[l,r]区间范围内（路径长度至少为1）
第一行输入三个整数 n, l, r
第二行输入一个长度为n的01串，第i个字符串代表i号节点的权值
接下来n - 1 行美行输入两个正整数u和v代表u节点和v节点间有一条边连接
4 4 5
1010
1 2
2 3
3 4
输出：3
想请问一下各位大佬为什么我这样的写法通过用例0%呢？
非常感谢！
import sys
from collections import Counter, defaultdict
if __name__ == "__main__":
line = sys.stdin.readline().strip()
n, l, r = tuple(map(int, line.split()))
matrix = []
line = sys.stdin.readline().strip()
val = [0]
for i in range(n):
val.append(line[i])
adj = defaultdict(list)
check = defaultdict(int)
# Set up Graph
for _ in range(n - 1):
line = sys.stdin.readline().strip()
e1, e2 = tuple(map(int, line.split()))
adj[e1].append(e2)
adj[e2].append(e1)
check[e1] += 1
check[e2] += 1
root = -1
# Find the root and build the tree
for k, v in check.items():
if v == 1:
root = k
break
trees = []
def dfs(root, parent):
trees.append(root)
for child in adj[root]:
if child != parent:
dfs(child, root)
dfs(root, -1)
def solution():
ans = 0
dp = [[0 for _ in range(len(trees))] for _ in range(len(trees))]
for i, num in enumerate(trees):
dp[i][i] = int(val[num])
for i in range(len(trees)):
for j in range(i + 1, len(trees)):
dp[i][j] = (dp[i][j - 1] << 1) + dp[j][j]
if l <= dp[i][j] <= r:
ans += 1
# Reverse value of dp[i][j] (Reversed Direction)
# Zero Padding before reverse
st = bin(dp[i][j])[2:]
if len(st) < j - i + 1:
st = '0' * (j - i + 1 - len(st)) + st
st = st[::-1]
if l <= int(st, 2) <= r:
ans += 1
return ans
print(solution())评论 (6)
