题解 | 游游的二进制树

#include <iostream>
#include <vector>
#include <string>
#include <functional>

using i64 = long long;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n;
  i64 l,r;
  std::cin >> n >> l >> r;

  std::string s;
  std::cin >> s;

  std::vector<std::vector<int>> adj(n);
  for(int i = 0; i < n-1; i++){
    int u,v;
    std::cin >> u >> v;
    u--,v--;

    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  int ans = 0;
  std::function<void(int,int,int,i64)> dfs = [&](int u,int fa,int cnt,i64 cur){
    if(cur > r){
      return;
    }
    if(cur >= l && cnt > 0){
      ans++;
    }

    for(const auto& v:adj[u]){
      if(v == fa){
        continue;
      }

      dfs(v,u,cnt+1,(cur<<1)+s[v]-'0');
    }
  };

  for(int u = 0; u < n; u++){
    dfs(u,-1,0,s[u]-'0');
  }

  std::cout << ans << "\n";
}

import sys
sys.setrecursionlimit(100000)

input = lambda : sys.stdin.readline().strip()

n,l,r = map(int,input().split())

s = input()

adj = [[] for i in range(n)]

for i in range(n-1):
  u,v = map(lambda x: int(x)-1,input().split())
  adj[u].append(v)
  adj[v].append(u)

ans = 0
def dfs(u,fa,cnt,cur):
  global ans
  if cur > r:
    return
  if cur >= l and cnt > 0:
    ans += 1
  for v in adj[u]:
    if v == fa:
      continue
    dfs(v,u,cnt+1,(cur<<1) | (ord(s[v])-ord('0')))

for i in range(n):
  dfs(i,-1,0,ord(s[i])-ord('0'))

print(ans)